Farmer John 的农场由 $N$ 个牧场 ($2 \leq N \leq 10^5$) 和连接它们的 $N-1$ 条道路组成，使得任意两个牧场之间都是连通的。也就是说，这个农场是一棵树。但在处理了 28 年因树结构而不可避免地产生的棘手算法问题后，FJ 认为树形的农场实在太复杂了。他认为在路径上的算法问题会更简单。

因此，他的计划是将所有道路划分为若干条路径，并将这些路径的维护责任分配给他的农场助手们。他不关心路径的数量。然而，他希望确保这些路径尽可能长，这样就没有助手能通过渐进低效的算法蒙混过关了！

请帮助 Farmer John 确定最大的正整数 $K$，使得所有道路可以被划分为长度至少为 $K$ 的路径。

SCORING

• 测试点 2-4：树是一个星形图；至多有一个顶点的度数大于 2。
• 测试点 5-8：满足 $N \leq 10^3$。
• 测试点 9-15：无额外限制。

输入格式

第一行包含一个整数 $N$。

接下来的 $N-1$ 行，每行包含两个用空格分隔的整数 $a$ 和 $b$，描述连接顶点 $a$ 和 $b$ 的一条边。$a$ 和 $b$ 均在 $1 \ldots N$ 的范围内。

输出格式

输出 $K$。

样例

输入格式 1

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

输出格式 1

3

说明

一种可能的路径划分方案如下： $$2-1-6-7-8, 3-1-4-5$$