The following is an implementation of a Disjoint Set Union (DSU):

N = read_integer()
parent = array(N, -1)

find(v):
    if parent[v] == -1:
        return v
    else:
        return find(parent[v])
union(a,b):
    parent[find(b)] = find(a)

for i = 0 to N-2:
    A_i = read_integer()
    B_i = read_integer()
    union(A_i,B_i)

The input to this code is a tree with nodes labeled from $0$ to $n-1$. For each edge $(A_i, B_i)$ read, the code merges the connected components containing $A_i$ and $B_i$ using the DSU. However, there is a problem with this code: its find(v) function does not implement path compression, so its complexity is incorrect.

As a problem setter for the provincial selection, you certainly cannot allow a DSU with incorrect complexity to pass your problem.

Given a tree, you can reorder the edges arbitrarily and swap $A_i$ and $B_i$ for each edge (or choose not to swap them). Find the maximum number of times find(v) is called by the code above.

Input

The first line contains a positive integer $n$, representing the number of nodes.

The next $n-1$ lines each contain two non-negative integers $A_i, B_i$, representing an edge.

Output

Output a single positive integer representing the answer.

Examples

Input 1

3
0 1
0 2

Output 1

5

Note 1

The reordered input is:

3
1 0
0 2

Input 2

10
0 1
0 2
1 3
0 4
4 5
0 6
5 7
7 8
7 9

Output 2

41

Input 3

See the provided files.

Constraints

For all test cases, it is guaranteed that $1\le n\le 2000$ and $0\le A_i, B_i\le n-1$. It is guaranteed that the input is a tree.