Little penguin Polo has got a tree — a non-directed connected acyclic graph, containing *n* nodes and *n* - 1 edges. We will consider the tree nodes numbered by integers from 1 to *n*.

Today Polo wonders, how to find the number of pairs of paths that don't have common nodes. More formally, he should find the number of groups of four integers *a*, *b*, *c* and *d* such that:
 -  1 ≤ *a* &lt; *b* ≤ *n*; -  1 ≤ *c* &lt; *d* ≤ *n*; -  there's no such node that lies on both the shortest path from node *a* to node *b* and from node *c* to node *d*. 
The shortest path betweem two nodes is the path that is shortest in the number of edges.

Help Polo solve this problem.
The first line contains integer *n* (1 ≤ *n* ≤ 80000) — the number of tree nodes. Each of the following *n* - 1 lines contains a pair of integers *u*<sub class="lower-index">*i*</sub> and *v*<sub class="lower-index">*i*</sub> (1 ≤ *u*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub> ≤ *n*; *u*<sub class="lower-index">*i*</sub> ≠ *v*<sub class="lower-index">*i*</sub>) — the *i*-th edge of the tree.

It is guaranteed that the given graph is a tree.
def dfs(x, px):
    global f, t
    ii = last[x]
    t[x] = 1
    f[x] = 0
    while ii:
        y = g[ii]
        if y != px:
            dfs(y, x)
            f[x] += t[x] * t[y]
            t[x] += t[y]
        ii = pred.get(ii, 0)

def dfs2(x, px):
    global o
    ii = last[x]
    while ii:
        y = g[ii]
        if y != px:
            o[y] = o[x] + f[y]
            dfs2(y, x)
        ii = pred.get(ii, 0)

n = int(input())
f = [0] * (n + 1)
o = [0] * (n + 1)
t = [0] * (n + 1)
last = {}
pred = {}
g = [0] * (2 * n + 1)
res = 0
kg = 0

for i in range(1, n):
    x, y = map(int, input().split())
    kg += 1
    g[kg] = y
    pred[kg] = last.get(x, 0)
    last[x] = kg
    kg += 1
    g[kg] = x
    pred[kg] = last.get(y, 0)
    last[y] = kg

dfs(1, 0)
o[1] = f[1]
dfs2(1, 0)

res = int(n) * (n - 1) // 2
res = res * res

for i in range(1, n + 1):
    res = res + f[i] * (o[i] * 2 - f[i] - t[i] * (n - t[i])) - o[i] * (n - 1)

print(res)