配点 : $1400$ 点

問題文

以下のように、木がウニ度 $k$ であるということを再帰的に定義します。

• $1$ 頂点からなる木はウニ度 $0$ の木である。
• ウニ度 $k$ の木を $0$ 個以上と、ひとつの頂点 $v$ を用意する。用意した各ウニ度 $k$ の木から頂点をひとつずつ選び、その選んだ頂点と $v$ を辺で結ぶ。こうしてできた木はウニ度 $k+1$ の木である。

ウニ度 $k$ の木はウニ度 $k+1,k+2,...$ の木でもあることが証明できます。

$N$ 頂点からなる木が与えられます。 この木の頂点には $1$ から $N$ までの番号がついており、$N-1$ 本の辺のうちの $i$ 本目は頂点 $a_i$ と $b_i$ を結んでいます。

与えられた木がウニ度 $k$ であるような最小の $k$ を求めてください。

制約

• $2 \leq N \leq 10^5$
• $1 \leq a_i, b_i \leq N(1 \leq i \leq N-1)$
• 与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $b_1$

:

$a_{N-1}$ $b_{N-1}$

出力

与えられた木がウニ度 $k$ であるような最小の $k$ を出力せよ。

7
1 2
2 3
2 4
4 6
6 7
7 5

2

頂点 $1$ からなるウニ度 $0$ の木と、頂点 $3$ からなるウニ度 $0$ の木と、頂点 $4$ からなるウニ度 $0$ の木と、 頂点 $2$ を組み合わせることで頂点 $1,2,3,4$ からなるウニ度 $1$ の木を作ることができ、

頂点 $5$ からなるウニ度 $0$ の木と、 頂点 $7$ を組み合わせることで頂点 $5,7$ からなるウニ度 $1$ の木を作ることができ、

頂点 $1,2,3,4$ からなるウニ度 $1$ の木と、頂点 $5,7$ からなるウニ度 $1$ の木と、 頂点 $6$ を組み合わせることで頂点 $1,2,3,4,5,6,7$ からなるウニ度 $2$ の木を作ることができます。

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

3