Description

First, you are given a tree with $n$ nodes rooted at $1$, called the “unit tree”.

Now there are $n$ trees with exactly the same structure as the “unit tree”. You need to connect these $n$ trees together using $n - 1$ edges.

For convenience, use the notation $(a,b)$ to represent: in the tree represented by node $a$, the node whose label is $b$.

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 nodes $(i,1)$ and $(f_i,f_i)$. Here $f_i$ is the parent of node $i$ in the “unit tree”.

After connecting the $n$ trees, you get a tree with $n^2$ nodes. Find the maximum number of nodes on a simple path between two nodes in this tree.

Input Format

The first line contains a positive integer $n$, 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 one line with a positive integer, the maximum number of nodes on a simple path between two nodes in the tree.

3
1 2
1 3

5

5
1 2
1 3
2 4
2 5

9

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

11

5
1 2
2 3
2 4
2 5

8

Hint

Sample Explanation

Sample #1

Sample #2: As shown in the figure below, the path with endpoints $(3,4)$ and $(4,4)$ contains $9$ nodes, and its length is $9$.

Sample #3: As shown in the figure below, choose $(6,6)$ and $(9,9)$, and it contains $11$ nodes.

In fact, for any two orange nodes whose lowest common ancestor is $1$, the answer is always $11$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata: $1\leq n\leq10^6$, and node labels are between $1$ and $n$.

This problem may be slightly tight on constants.

The time limit has been reduced to $1\text{s}$ for the following reasons:

• The discussion board believes this problem is the same as an existing one. To prevent the so-called “enhanced version” $O(n\log n)$ solution from directly passing this problem, the time limit was reduced.

• The optimal solution can run within $200\text{ms}$.

• Because the author is lazy and did not want to change $n\le10^6\rightarrow n\le10^7$, they can only reduce the time limit to block the so-called original-problem solution (which is actually incorrect).

Translated by ChatGPT 5