Background

Mount Fuji, called “the sacred mountain” by locals, is a dormant volcano. Its most recent eruption was $300$ years ago.

If you throw the elixir of immortality into such a mountain, it would probably erupt immediately. This explains why Tsukuyomi Iwakasa (Yueyanli) eventually disobeyed orders.

Problem Description

A “mountain” has a shape that is narrow at the top and wide at the bottom. Can we find a similar structure in a “tree”?

You are given a rooted tree $T$ of size $n$ with root $1$. You need to find the largest induced subtree whose widths are monotonically non-decreasing:

• Let this induced subtree be $T_0$, and it has $k$ levels.
• Define the depth of the root of $T_0$ to be $1$, and compute the depth $d_i$ of each node in $T_0$. Then define the width $w_i$ of level $i$ in $T_0$ as “the number of nodes with depth $i$”.
• You need to make $w_i$ monotonically non-decreasing, i.e., $w_1\le w_2\le \cdots \le w_k$.

Let the vertex set and edge set of the original tree be $V, E$. An induced subtree is a connected component of the original tree: its vertex set is $V_0\subseteq V$, and its edge set $E_0$ contains all edges in $E$ whose both endpoints are in $V_0$. The root of an induced subtree is the node among all its nodes that has the smallest depth in the original tree. $T$ itself can also be regarded as an induced subtree of itself.

As shown in the figure, the green region and the orange region are induced subtrees of the original tree. Their roots are $2$ and $13$, respectively.

Note: The definition of an induced subtree is slightly different from the definition of a subtree. Please do not confuse the two.

Find the maximum size of an induced subtree that satisfies the condition.

Input Format

The first line contains a positive integer $n$, the size of the whole tree.

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

Output Format

Output one line containing one integer, the maximum size of an induced subtree that satisfies the condition.

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

9

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

16

Hint

Sample Explanation

As shown in the figure, the gray nodes are the induced subtrees chosen in the two samples.

• In sample $1$, the induced subtree found has widths $\{1,2,3,3\}$ for each level.
• In sample $2$, the induced subtree found has widths $\{1,2,4,4,5\}$ for each level.

Constraints and Conventions

For all testdata, $1\le n\le 5\times 10^5$.

Translated by ChatGPT 5