#39 「 天天和树 」

统计

一个树由$n$个点,$n-1$条边组成,结点编号为$1 ... n$。树上任意两个点之间路径唯一。

定义一个点到一条路径的距离为:该点到路径上最近的一个点需要经过的边的数量。

现在想知道怎样选两个点确定一条路径,使得距离这个路径最远的点尽量近。要求你输出距离路径最远的点距离路径的距离。

输入格式

第一行一个整数$n$。其中$1 \le n \le 100,000$

接下来$n-1$行,每行两个整数$u$和$v$,表示结点$u$和结点$v$之间有一条边。

输出格式

一行一个整数,为题目要求的答案。

样例数据

input

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

output

2

样例解释

可以选择3到7作为一条链,那么此时距离这条链最远的点是5,距离为2。可以发现不存在其他的一条链,使得最远点的距离更短。

数据规模与约定

对于10\%的数据,保证$n = 99998$,且树退化成一条链。

对于另外30\%的数据,保证$n=100$。

对于另外30\%的数据,保证$n = 99999$,且最终答案小于等于$5$。

对于剩余的30\%的数据,保证$n = 100000$。

时间限制:1s

空间限制:512MB

Author: Chenyao2333