[AGC009D] Uninity

题意翻译

定义一个单独的节点为一棵Uninity 0的树。 将$x(x \geq 0)$棵Uninity k的树全部连到一个节点上形成的树,称之为一棵Uninity k+1的树。 显然,一棵Uninity k的树,同样也是一棵Uninity k+1,k+2,k+3...的树。 现在给你一棵树,求一个最小的k使得这棵树是一棵Uninity k的树。

题目描述

[problemUrl]: https://atcoder.jp/contests/jrex2017/tasks/agc009_d 以下のように、木がウニ度 $ 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 $ を求めてください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ : $ a_{N-1} $ $ b_{N-1} $

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

2

输入样例 #2

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

输出样例 #2

3

说明

### 制約 - $ 2\ ≦\ N\ ≦\ 10^5 $ - $ 1\ ≦\ a_i,\ b_i\ ≦\ N(1\ ≦\ i\ ≦\ N-1) $ - 与えられるグラフは木である。 ### Sample Explanation 1 頂点 $ 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 $ の木を作ることができます。