Problem Description

Snuke, a beginner in programming, wrote the following code:

N = read_integer()

parent = array(N, -1) // Create an array parent of length N and initialize all elements to -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)

This is a program that takes the information of a tree with $ N $ vertices and simply connects edges using Union-Find.

Ringo, a programming master, noticed a flaw in this program. Namely, no optimizations are applied to the Union-Find.

Now, Ringo has a tree $ T $ with $ N $ vertices. The vertices of $ T $ are numbered from $ 0 $ to $ N-1 $, and the edges are numbered from $ 0 $ to $ N-2 $. Edge $ i $ connects vertex $ A_i $ and vertex $ B_i $.

Ringo is about to provide $ T $ as input to Snuke's program. Before doing so, Ringo can freely rearrange the numbers of the edges and the order of the endpoints of the edges.

Ringo wants to maximize the number of times the find function is called to demonstrate the inefficiency of Snuke's program. Find the maximum number of times the find function is called.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_0 $ $ B_0 $ $ A_1 $ $ B_1 $ $\vdots$ $ A_{N-2} $ $ B_{N-2} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2
0 1

Sample Output #1

2

Sample Input #2

3
0 1
0 2

Sample Output #2

5

Sample Input #3

5
0 1
0 2
0 3
3 4

Sample Output #3

13

Sample Input #4

20
6 16
10 6
16 8
1 5
9 4
5 3
13 16
19 10
12 2
14 10
12 18
0 2
15 16
12 7
11 14
1 10
6 4
17 8
12 1

Sample Output #4

148

Notes/Hints

Constraints

• $2 \leq N \leq 2000$
• $0 \leq A_i, B_i \leq N-1$
• $A_i \neq B_i$
• The input graph is a tree

Sample Explanation 1

The find function is always called $ 2 $ times.

Sample Explanation 2

By swapping the order of the endpoints of edge $ 0 $ and creating the following input, the find function is called $ 5 $ times:

3
1 0
0 2

Sample Explanation 3

By appropriately swapping the order of the edges and the endpoints of the edges, creating the following input, the find function is called $ 13 $ times:

5
3 0
4 3
1 0
0 2

见题面 Input 部分

见题面 Output 部分