CodeEff/ECCO huggingface dataset:
# Original solution
import math
from functools import reduce

k=int(eval(input()))
ans=0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=(gcd(a,b,c))
print(ans)

# Optimized solution
import itertools
import math
from functools import reduce

k=int(eval(input()))
l=list(range(1,k+1))
ans=0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for i in itertools.product(l,repeat=3):
    ans+=(gcd(i[0],i[1],i[2]))
print(ans)
# Original solution
import math
K = int(eval(input()))
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += math.gcd(i+1, math.gcd(j+1, k+1))
print(ans)


# Optimized solution
import math
K = int(eval(input()))
ans = 0
for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            if (i == j) and (j == k):
                ans += math.gcd(i, math.gcd(j, k))
            elif (i == j) or (j == k):
                ans += 3 * math.gcd(i, math.gcd(j, k))
            else:
                ans += 6 * math.gcd(i, math.gcd(j, k))
print(ans)
# Original solution
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(eval(input()))
ans = 0
for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      ans += gcd(a,b,c)
print(ans)

# Optimized solution
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(eval(input()))
ans = 0
for a in range(1, k+1):
  for b in range(a, k+1):
    for c in range(b, k+1):
      t = len({a,b,c})
      if t == 3:
        ans += gcd(a,b,c) * 6
      elif t == 2:
        ans += gcd(a,b,c) * 3
      else:
        ans += gcd(a,b,c)
        
print(ans)
# Original solution
import math
n=int(eval(input()))
s=0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      s += math.gcd(i,math.gcd(j,k))
print(s)


# Optimized solution
import math
  
def main():
  k=int(eval(input()))
  cur=0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        cur+=math.gcd(math.gcd(a,b),c)
        
  return cur
print((main()))
# Original solution
import math
from functools import reduce
n = int(eval(input()))
ans = 0
li = []
buf = n

for i in range(1,n+1):
    for j in range(1,n+1):
        tmp = math.gcd(i,j)
        li.append(tmp)
for i in range(len(li)):
    for j in range(1,n+1):
        ans += math.gcd(li[i],j)

print(ans)


# Optimized solution
import math
from functools import reduce
n = int(eval(input()))
ans = 0
li = []
buf = n

def gcd(*numbers):
    return reduce(math.gcd,numbers)

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += gcd(i,j,k)

print(ans)
# Original solution
#!/usr/bin/env python3
import math
MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

K = int(eval(input()))

ans = 0
for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            if i==j and i==k: g = i
            elif (i==j and i!=k):
                g = math.gcd(i,math.gcd(j,k))*3
            elif (i==k and i!=j):
                g = math.gcd(i,math.gcd(j,k))*3
            elif (j==k and i!=j):
                g = math.gcd(i,math.gcd(j,k))*3
            else : g = math.gcd(i,math.gcd(j,k))*6
            ans += g
print(ans)


# Optimized solution
import math

K = int(eval(input()))

ans = 0
for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            if i==j and i==k: g = i
            elif (i==j and i!=k):
                g = math.gcd(i,math.gcd(j,k))*3
            elif (i==k and i!=j):
                g = math.gcd(i,math.gcd(j,k))*3
            elif (j==k and i!=j):
                g = math.gcd(i,math.gcd(j,k))*3
            else : g = math.gcd(i,math.gcd(j,k))*6
            ans += g
print(ans)
# Original solution
from math import gcd
n = int(eval(input()))
ans = 0

for a in range(1,n+1):
    for b in range(1,n+1):
        for c in range(1,n+1):
            ans += gcd(a,gcd(b,c))
print(ans)

# Optimized solution
from math import gcd
n = int(eval(input()))
ans = 0

for a in range(1,n+1):
    for b in range(1,n+1):
        for c in range(1,n+1):
            ans += gcd(c,gcd(a,b))
print(ans)
# Original solution
import sys

CharToSign = {
    "A": "00000", "B": "00001", "C": "00010", "D": "00011",
    "E": "00100", "F": "00101", "G": "00110", "H": "00111",
    "I": "01000", "J": "01001", "K": "01010", "L": "01011",
    "M": "01100", "N": "01101", "O": "01110", "P": "01111",
    "Q": "10000", "R": "10001", "S": "10010", "T": "10011",
    "U": "10100", "V": "10101", "W": "10110", "X": "10111",
    "Y": "11000", "Z": "11001", " ": "11010", ".": "11011",
    ",": "11100", "-": "11101", "'": "11110", "?": "11111",
}
SignToChar = {
    "101": " ", "000000": "'", "000011": ",", "10010001": "-",
    "010001": ".", "000001": "?", "100101": "A", "10011010": "B",
    "0101": "C", "0001": "D", "110": "E", "01001": "F",
    "10011011": "G", "010000": "H", "0111": "I", "10011000": "J",
    "0110": "K", "00100": "L", "10011001": "M", "10011110": "N",
    "00101": "O", "111": "P", "10011111": "Q", "1000": "R",
    "00110": "S", "00111": "T", "10011100": "U", "10011101": "V",
    "000010": "W", "10010010": "X", "10010011": "Y", "10010000": "Z",
}

for line in sys.stdin:
    line = line[:-1]

    sign = []
    for char in line:
        convert = CharToSign[char]
        sign.append(convert)

    sign = "".join(sign)

    startIndex = 0
    endIndex = 3

    string = []

    length = len(sign)
    while endIndex <= length:

        part = sign[startIndex:endIndex]
        if part in SignToChar:
            convert = SignToChar[part]
            string.append(convert)
            startIndex = endIndex
            endIndex += 3
        else:
            endIndex += 1

    string = "".join(string)
    print(string)



# Optimized solution
import sys

CharToSign = {
    "A": "00000", "B": "00001", "C": "00010", "D": "00011",
    "E": "00100", "F": "00101", "G": "00110", "H": "00111",
    "I": "01000", "J": "01001", "K": "01010", "L": "01011",
    "M": "01100", "N": "01101", "O": "01110", "P": "01111",
    "Q": "10000", "R": "10001", "S": "10010", "T": "10011",
    "U": "10100", "V": "10101", "W": "10110", "X": "10111",
    "Y": "11000", "Z": "11001", " ": "11010", ".": "11011",
    ",": "11100", "-": "11101", "'": "11110", "?": "11111",
}
SignToChar = {
    "101": " ", "000000": "'", "000011": ",", "10010001": "-",
    "010001": ".", "000001": "?", "100101": "A", "10011010": "B",
    "0101": "C", "0001": "D", "110": "E", "01001": "F",
    "10011011": "G", "010000": "H", "0111": "I", "10011000": "J",
    "0110": "K", "00100": "L", "10011001": "M", "10011110": "N",
    "00101": "O", "111": "P", "10011111": "Q", "1000": "R",
    "00110": "S", "00111": "T", "10011100": "U", "10011101": "V",
    "000010": "W", "10010010": "X", "10010011": "Y", "10010000": "Z",
}

for line in sys.stdin:
    line = line[:-1]

    sign = ""
    for char in line:
        sign += CharToSign[char]

    string = ""
    part = ""

    for item in sign:
        part += item

        if part in SignToChar:
            string += SignToChar[part]
            part = ""

    print(string)
# Original solution
N = eval(input())
if int(N) == 1:
    print("Hello World")
else:
    A = int(eval(input()))
    B = int(eval(input()))
    print((A + B))
        

# Optimized solution
N = int(eval(input()))
if N == 1:
    print("Hello World")
else:
    A = int(eval(input()))
    B = int(eval(input()))
    print((A + B))
# Original solution
n = int(eval(input()))
if n==1:
    print('Hello World')
else:
    a = int(eval(input()))
    b = int(eval(input()))
    print((a+b))


# Optimized solution
n = int(eval(input()))
if n==1:
    print('Hello World')
    exit()
a = int(eval(input()))
b = int(eval(input()))
print((a+b))
# Original solution
import math
def ip():return int(eval(input()))
def imp():return list(map(int,input().split()))

n=ip()
if n==1:print("Hello World")
else:
    a=ip()
    b=ip()
    print((a+b))

# Optimized solution
n=int(eval(input()))
if n==1:print("Hello World")
else:print((int(eval(input()))+int(eval(input()))))
# Original solution
N = int(eval(input()))
if N == 1:
  print("Hello World")
else:
  A = int(eval(input()))
  B = int(eval(input()))
  print((A+B))

# Optimized solution
#coding: utf-8
N = int(eval(input()))
if N == 1:
    print("Hello World")
else:
    a = int(eval(input()))
    b = int(eval(input()))
    print((a+b))
# Original solution
import itertools
import math
import fractions
import functools
import copy

n = int(eval(input()))

if n == 1:
    print("Hello World")
else:
    a = int(eval(input()))
    b = int(eval(input()))
    print((a+b))


# Optimized solution
def main():
    n = int(eval(input()))
    # h, w, k = map(int, input().split())
    # a = list(map(int, input().split()))
    # s = input()

    if n == 1:
        print("Hello World")
    else:
        a = int(eval(input()))
        b = int(eval(input()))
        print((a+b))


if __name__ == '__main__':
    main()
# Original solution
print(eval(input())+eval(input())if eval(input())-1else'Hello World')

# Optimized solution
print(eval(input())+eval(input())if~-eval(input())else'Hello World')
# Original solution
i=lambda:int(eval(input()));print((i()+i()if~-i()else'Hello World'))

# Optimized solution
print('Hello World'*-~-~-eval(input())or eval(input())+eval(input()))
# Original solution
def toInteger(string):
  integer = int(string)
  return integer

def myInput():
  s = eval(input())
  i = toInteger(s)
  return i

def isEqual(a, b):
  try:
    1 / (a - b)
  except:
    return True
  return False

def isValue1(v):
  boolean = isEqual(v, 1)
  if isEqual(boolean, True) == True:
    return True
  elif isEqual(boolean, False) == True:
    return False
  else:
    None

def isValue2(v):
  boolean = isEqual(v, 2)
  if isEqual(boolean, True) == True:
    return True
  elif isEqual(boolean, False) == True:
    return False
  else:
    None

def printString(String):
  print(String)

def printHelloWorld():
  printString('Hello World')
  
def printInteger(integer):
  print(integer)

def sumTwoValues(a, b):
  c = a + b
  return c

def solve(v):
  boolean1 = isValue1(v)
  boolean2 = isValue2(v)
  if isEqual(boolean1, True) == True:
    printHelloWorld()
  elif isEqual(boolean2, True) == True:
    a = myInput()
    b = myInput()
    c = sumTwoValues(a, b)
    printInteger(c)
  else:
    None

a = myInput()
solve(a)

# Optimized solution
def toInteger(string):
  try:
    integer = int(string)
    return integer
  except:
    print('Number Format Exception')
    exit()

def myInput():
  s = eval(input())
  i = toInteger(s)
  return i

def isEqual(a, b):
  try:
    1 / (a - b)
  except:
    return True
  return False

def isValue1(v):
  boolean = isEqual(v, 1)
  if isEqual(boolean, True) == True:
    return True
  elif isEqual(boolean, False) == True:
    return False
  else:
    None

def isValue2(v):
  boolean = isEqual(v, 2)
  if isEqual(boolean, True) == True:
    return True
  elif isEqual(boolean, False) == True:
    return False
  else:
    None

def printString(String):
  print(String)

def printHelloWorld():
  printString('Hello World')
  
def printInteger(integer):
  print(integer)

def sumTwoValues(a, b):
  c = a + b
  return c

def solve(v):
  boolean1 = isValue1(v)
  boolean2 = isValue2(v)
  if isEqual(boolean1, True) == True:
    printHelloWorld()
  elif isEqual(boolean2, True) == True:
    a = myInput()
    b = myInput()
    c = sumTwoValues(a, b)
    printInteger(c)
  else:
    None

def main():
  a = myInput()
  solve(a)
  
main()
# Original solution
n = int(input())
if n == 1: print('Hello World')
elif n == 2: print(int(input())+int(input()))

# Optimized solution
print('Hello World' if int(input()) == 1 else (int(input())+int(input())))
# Original solution
N = int(eval(input()))
if(N == 1):
  print("Hello World")
else:
  print((int(eval(input())) + int(eval(input()))))

# Optimized solution
def ans():
  N = int(eval(input()))
  if(N == 1):
    print("Hello World")
  else:
    A = int(eval(input()))
    B = int(eval(input()))
    print((A+B))
ans()
# Original solution
age = int(eval(input()))

if age == 1:
    print('Hello World')
elif age == 2:
    a = int(eval(input()))
    b = int(eval(input()))
    print((a + b))

# Optimized solution
n = int(eval(input()))

if n == 1:
    print('Hello World')
else:
    a = int(eval(input()))
    b = int(eval(input()))
    print((a + b))
# Original solution
*a,=list(map(int,open(0).read().split()))
print((a[1]+a[2]if a[0]>1else'Hello World'))

# Optimized solution
i=input;print((eval(i()+'+'+i())if'1'<i()else'Hello World'))
# Original solution
if int(eval(input())) == 1:
    print('Hello World')
else:
    print((int(eval(input()))+int(eval(input()))))

# Optimized solution
n = int(eval(input()))
if n == 1:
    print('Hello World')
else:
    a = int(eval(input()))
    b = int(eval(input()))
    print((a + b))
# Original solution
n = int(eval(input()))
tree = [[] for _ in range(n)]
for i in range(n-1):
  v, w = list(map(int, input().split()))
  if v > w:
    v, w = w, v
  tree[w-1].append(v-1)
  
ans = 0
count = 0
for i in range(n):
  count += i+1
  for v in tree[i]:
    count -= v+1 
  ans += count
  
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

def main():
  n = int(eval(input()))
  tree = [[] for _ in range(n)]
  for i in range(n-1):
    v, w = list(map(int, input().split()))
    if v > w:
      v, w = w, v
    tree[w-1].append(v-1)
  
  ans = 0
  count = 0
  for i in range(n):
    count += i+1
    for v in tree[i]:
      count -= v+1
    ans += count
  
  print(ans)
  
if __name__ == "__main__":
  main()
# Original solution
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def sum_between(a, b):
    if a > b:a, b = b, a
    return (b-a+1) * (b+a) // 2

def run():
    N = int(eval(input()))
    n_dots = 0
    for i in range(1, N+1):
        n_dots += (1+i) * i // 2
    #print(n_dots)
    ans = (N-1) * (N+1) * N // 2
    #print(ans)
    for i in range(N-1):
        u, v = list(map(int, input().split()))
        l, r = min(u, v), max(u, v)
        tmp = 0
        if l > 1: tmp += sum_between(r-1, r-l+1)
        tmp += r-l
        tmp += sum_between(N-l, 1)
        #print(tmp)
        ans -= tmp

    print((n_dots - ans))


    ans = (N-1) * N * N


if __name__ == "__main__":
    run()

# Optimized solution
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def sum_between(a, b):
    if a > b:a, b = b, a
    return (b-a+1) * (b+a) // 2

def run():
    N = int(eval(input()))
    n_dots = 0
    for i in range(1, N+1):
        n_dots += (1+i) * i // 2
    #print(n_dots)
    ans = (N-1) * (N+1) * N // 2
    #print(ans)
    for i in range(N-1):
        l, r = list(map(int, input().split()))
        if l > r: l,r = r,l
        tmp = 0
        if l > 1: tmp += sum_between(r-1, r-l+1)
        tmp += r-l
        tmp += sum_between(N-l, 1)
        #print(tmp)
        ans -= tmp

    print((n_dots - ans))


    ans = (N-1) * N * N


if __name__ == "__main__":
    run()
# Original solution
n = int(eval(input()))
a = [i+1 for i in range(n)]
b = [1]
for i in range(1,n):
  b.append(b[-1] + a[i])
c = [0]
for i in range(n-1):
  c.append(c[-1]+b[i])
#print(a)
#print(b)
#print(c)
ans = b[-1] + c[-1]
for _ in range(n-1):
  xy = list(map(int,input().split()))
  xy.sort()
  x,y = xy
  ans -= x * (n+1-y)
print(ans)

# Optimized solution
n = int(eval(input()))
ans = n*(n+1)*(n+2)//6
for i in range(n-1):
  xy = list(map(int,input().split()))
  ans -= min(xy) * (n+1-max(xy))
print(ans)
# Original solution
n=int(eval(input()))
a=0
for i in range(n):
  a+=(i+1)*(n-i)
for _ in range(n-1):
  u,v=list(map(int,input().split()))
  if u>v: u,v=v,u
  a-=u*(n-v+1)
print(a)

# Optimized solution
n=int(eval(input()))
a=sum(-~i*(n-i) for i in range(n))
for _ in range(n-1):
  u,v=list(map(int,input().split()))
  if u>v: u,v=v,u
  a-=u*(n-v+1)
print(a)
# Original solution
n=int(eval(input()))+1
a=(n**3-n)//6
for _ in range(n-2):
  u,v=list(map(int,input().split()))
  a-=min(u,v)*(n-max(u,v))
print(a)

# Optimized solution
n,*l=list(map(int,open(0).read().split()));n+=1;i=iter(l);print(((n**3-n)//6-sum(min(u,v)*(n-max(u,v))for u,v in zip(i,i))))
# Original solution
N = int(eval(input()))

ans = 0
for i in range(1, N + 1):
    ans += i * (N + 1 - i)

for i in range(N - 1):
    u, v = list(map(int, input().split()))
    u, v = min(u, v), max(u, v)
    ans -= (N - v + 1) * u

print(ans)


# Optimized solution
N,*t=list(map(int,open(0).read().split()))
t=iter(t)
print((N*(N+1)*(N+2)//6+sum([-min(a,b)*(N-max(a,b)+1) for a,b in zip(t,t)])))
# Original solution
n=int(eval(input()))
if n==1:
    print((1))
else:
    g=[list(map(int,input().split())) for i in range(n-1)]
    
    edge_sum=0
    
    for l in range(1,n+1):
        for r in range(l,n+1):
            edge_num=0
            edge_num += r-l+1
            for k in range(n-1):
                if l<=g[k][0]<=r and l<=g[k][1]<=r:
                    edge_num -= 1
            
            edge_sum +=edge_num
    print(edge_sum)

# Optimized solution
n=int(eval(input()))
ans=0
for i in range(1,n+1):
    ans += i*(i+1)/2
for i in range(n-1):
    u,v=list(map(int,input().split()))
    if u > v:
        u,v=v,u
    ans -= u*(n-v+1)
print((int(ans)))
# Original solution
# Union Find
class edge:
    def __init__(self, u, v):
        self.u = u
        self.v = v
    def min(self):
        return min(self.u, self.v)
    def max(self):
        return max(self.u, self.v)


# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


# 初期化
# 根なら-size,子なら親の頂点
N = int(eval(input()))

edge_list = []
for i in range(N - 1):
    u, v = list(map(int, input().split()))
    edge_list.append(edge(u - 1, v - 1))

ans_sum = 0
edge_list.append(edge(N, N))
upper_l_edge_list = sorted(edge_list, key=lambda e: -e.max())

for l in range(N):
    par = [-1] * N
    num_cc = 0
    upper_l_edge_list_copy = [e for e in upper_l_edge_list if e.min() >= l]
    ### upper_l_edge_list_copy.append(edge(N, N))
    ### upper_l_edge_list = sorted(upper_l_edge_list_copy, key=lambda e: -e.max()) ###

    for r in range(l, N):
        size = 0
        # print([(e.u, e.v) for e in upper_l_edge_list])
        while upper_l_edge_list_copy[-1].max() <= r:
            e = upper_l_edge_list_copy.pop()
            if not same(e.u, e.v):
                size += 1
            unite(e.u, e.v)
        num_cc = num_cc - size + 1
        # print(l, r, num_cc, "size_r", size)
        ans_sum += num_cc

print(ans_sum)


# Optimized solution
class edge:
    def __init__(self, u, v):
        self.u = u
        self.v = v
    def min(self):
        return min(self.u, self.v)
    def max(self):
        return max(self.u, self.v)

N = int(eval(input()))
 
edge_list = []
for i in range(N - 1):
    u, v = list(map(int, input().split()))
    edge_list.append(edge(u - 1, v - 1))
 
ver_num = int(N * (N + 1) * (N + 2) / 6)
 
edge_num = 0
for e in edge_list:
    edge_num += (N + 1 - (e.max() + 1)) * (e.min() + 1)
    
print((ver_num - edge_num))
# Original solution
n = int(eval(input()))
V = E = 0
for d in range(1,n+1): V += d * (d + 1) // 2
for _ in range(n-1):
    a, b = list(map(int, input().split()))
    if a > b: a, b = b, a
    E += a * (n - b + 1)
print((V - E))


# Optimized solution
n = int(eval(input()))
V = n*(n+1)*(n+2)//6; E = 0
for _ in range(n-1):
    u, v = list(map(int, input().split()))
    if u > v: u, v = v, u
    E += u * (n - v + 1)
print((V - E))
# Original solution
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(eval(input()))
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a,b = list(map(int,input().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    parents = [-1] * N
    stack = [0]
    while stack:
        v = stack.pop()
        for e in G[v]:
            if e == 0 or parents[e] >= 0:
                continue
            parents[e] = v
            stack.append(e)
    
    ans = N
    for i in range(1,N):
        if parents[i] > i:
            ans += (parents[i] - i) * (i + 1)
        else:
            ans += (i - parents[i]) * (N - i)
    print(ans)
if __name__ == '__main__':
    main()

# Optimized solution
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(eval(input()))
    ans = 0
    for i in range(N):
        ans += (i + 1)*(N - i)
    for _ in range(N - 1):
        a,b = list(map(int,input().split()))
        a -= 1
        b -= 1
        if a > b:
            a,b = b,a
        ans -= (N - b) * (a + 1)
    print(ans)
if __name__ == '__main__':
    main()
# Original solution
N=int(eval(input()))
l = [list(map(int, input().split())) for l in range(N-1)]
c=0
for i in range(N-1):c+=min(l[i])*(N+1-max(l[i]))
print((N*(N+1)*(N+2)//6-c))

# Optimized solution
N=int(eval(input()))
l = [sorted(list(map(int, input().split()))) for l in range(N-1)]
c=0
for i in range(N-1):c+=l[i][0]*(N+1-l[i][1])
print((N*(N+1)*(N+2)//6-c))
# Original solution
N = int(eval(input()))
count = [1 for _ in range(N+2)]
count[-1] = 0
count[0] = 0
nextpoint = [[] for _ in range(N+1)]
for _ in range(N-1):
  u, v = list(map(int, input().split()))
  if u > v:
    nextpoint[v].append(u)
  else:
    nextpoint[u].append(v)

#print(nextpoint)
for k in range(N+1):
  if len(nextpoint[k]) > 0:
    nextpoint[k].sort()

#print(nextpoint)
for k in range(1, N):
  for item in nextpoint[k]:
    count[item] -= 1

#print(count)
ans = 0
for k in range(1, N):
  count[k+1] += count[k]
#print(count)
ans = sum(count) #L=1
#print(ans)
before = ans
for k in range(1, N):#L=2~N
  before -= N-k+1
  for item in nextpoint[k]:
    before += N+1-item
  ans += before
print(ans)

  

# Optimized solution
N = int(eval(input()))
count = [1 for _ in range(N+2)]
count[-1] = 0
count[0] = 0
nextpoint = [[] for _ in range(N+1)]
for _ in range(N-1):
  u, v = list(map(int, input().split()))
  if u > v:
    nextpoint[v].append(u)
  else:
    nextpoint[u].append(v)



#print(nextpoint)
for k in range(1, N):
  for item in nextpoint[k]:
    count[item] -= 1

#print(count)
ans = 0
for k in range(1, N):
  count[k+1] += count[k]
#print(count)
ans = sum(count) #L=1
#print(ans)
before = ans
for k in range(1, N):#L=2~N
  before -= N-k+1
  for item in nextpoint[k]:
    before += N+1-item
  ans += before
print(ans)