Problem Description

First, a tree with $n$ nodes rooted at $1$ is given, defined as the "unit tree".

There are $n$ trees, each identical in structure to the "unit tree", and we need to connect these $n$ trees using $n-1$ edges.

For convenience, we use the notation $(a, b)$ to represent the node with number $b$ in the tree represented by node $a$.

The connection method is as follows:

1. Arrange the $n$ trees according to the structure of the "unit tree".

2. For each $i (1 < i \leq n)$, connect node $(i, 1)$ and node $(f_i, f_i)$, where $f_i$ represents the parent of node $i$ in the "unit tree".

Find the maximum number of nodes in the simple path between any two nodes in the tree that contains $n^2$ nodes after connecting the $n$ trees.

Input Format

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

The next $n-1$ lines each contain two positive integers $u, v$, representing an edge in the "unit tree".

Output Format

Output a single positive integer, representing the maximum number of nodes in the simple path between any two nodes in the tree.

Sample Input and Output

Sample Input #1

3
1 2
1 3

Sample Output #1

5

Sample Input #2

5
1 2
1 3
2 4
2 5

Sample Output #2

9

Sample Input #3

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

Sample Output #3

11

Sample Input #4

5
1 2
2 3
2 4
2 5

Sample Output #4

8

Notes

Sample Explanation

For Sample #1, refer to the image at this link.

For Sample #2, refer to the image at this link. The path between $(3,4)$ and $(4,4)$ contains 9 nodes, with a length of 9.

For Sample #3, refer to the image at this link. The path between $(6,6)$ and $(9,9)$ contains 11 nodes.

In fact, any two orange nodes with the nearest common ancestor as $1$ will yield an answer of 11.

Data Range

This problem is bundled with subtasks.

For 100% of the data: $1 \leq n \leq 10^6$, node numbers range from $1$ to $n$.

This problem may have tight time constraints.

The time limit is reduced to 1 second for the following reasons:

• The discussion forum suggests that this problem is similar to an existing one, and to prevent the so-called "enhanced version" with an $O(n \log n)$ solution from passing directly, the time limit is reduced.
• The optimal solution can run within 200ms.
• Due to the laziness of the problem setter, and the inability to increase $n \le 10^6$ to $n \le 10^7$, the time limit is reduced to block the so-called original problem solutions (which are actually incorrect).

见题面 Input 部分

见题面 Output 部分