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 calc(n):
    return n * (n - 1) // 2
def dfs(x, rt):
    arr[x] = 1
    sum = 0
    for y in gr[x]:
        if y != rt:
            dfs(y, x)
            arr[x] += arr[y]
            sum -= arr[y] * (arr[y] - 1) // 2
    sum += arr[x] * (arr[x] - 1) // 2
    global res
    res = res + sum * (2 * arr[x] * (n - arr[x]) + sum)
n = int(input())
gr = [[] for _ in range(n + 1)]
arr = [0] * (n + 1)
res = 0
for _ in range(n - 1):
    x, y = map(int, input().split())
    gr[x].append(y)
    gr[y].append(x)
dfs(1, 0)
print(calc(n) * calc(n) - res)# 1692692307.9671092