AT_agc009_d

题目描述

如下递归地定义一棵树的“ウニ度”$k$：

• 仅包含 $1$ 个顶点的树，其ウニ度为 $0$。
• 准备若干棵ウニ度为 $k$ 的树（可以为 $0$ 棵），再准备一个顶点 $v$。从每棵ウニ度为 $k$ 的树中各选一个顶点，并将这些顶点与 $v$ 分别用边连接。这样得到的树，其ウニ度为 $k+1$。

可以证明，ウニ度为 $k$ 的树同时也是ウニ度为 $k+1,k+2,\ldots$ 的树。

给定一棵包含 $N$ 个顶点的树。树的顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

请你求出使得该树为ウニ度 $k$ 的最小 $k$。

输入格式

输入按以下格式从标准输入读入：

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

输出格式

输出使得给定树为ウニ度 $k$ 的最小 $k$。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #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 \leq N \leq 10^5$
• $1 \leq a_i, b_i \leq N\ (1 \leq i \leq N-1)$
• 输入保证是一棵树。

样例解释 1

可以将顶点 $1$、$3$、$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$ 的树。