题目描述

题目译自 USACO 2020 Feburary Contest, Platinum Problem 1. Delegation

Farmer John 的 $N$ 片牧场由 $N-1$ 条道路连接而成，使得任意一片牧场与其他牧场都联通，形成了树状结构。在研究了由这树状结构产生的各种算法问题 $28$ 年后，他还是觉得农场的结构过于复杂，而他相信研究路径的算法问题更为简单。

因此，他的目标是把牧场间的道路分成一条条路径，然后指定这些路径在他贵重的农场工人的使用过程中起些什么作用。他不关心路径的数目，而是想要这些路径越长越好，使得没有农场工人可以用低效率的算法解决问题。

你的任务是帮 Farmer John 找出最大的整数 $K$ 使得每条道路恰好被分入一条路径中，且路径长度至少为 $K$。

译者注：此处最后一段已修改表述以使得更清晰，如有疑问请查阅原题。

输入格式

第一行一个整数 $N$。

接下来 $N-1$ 行每行两个以空格隔开的整数 $a,~b$，表示节点 $a$ 和节点 $b$ 之间有一条边。

输出格式

输出 $K$。

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

3

数据范围与提示

测试点 $2\ldots4$ 满足输入的结构形成了星状结构，即至多有一个节点的度数大于 2。

测试点 $5\ldots8$ 满足 $N\le 10^3$

测试点 $9\ldots15$ 无特殊限制。

对于 $100\%$ 的数据，有 $2\le N \le 10^5$。