题目描述

Farmer John 的 $N$ 片牧场由 $N-1$ 条道路连接，形成了一棵树。
在研究了这棵树结构产生的算法问题 $28$ 年后，他决定把道路划分成若干条路径，并希望这些路径尽可能长。

要求：

• 每条道路恰好属于一条路径；
• 路径的长度（经过的边数）至少为 $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 \to 1 \to 6 \to 7 \to 8$（长度 $4$）
• 路径 $3 \to 1 \to 4 \to 5$（长度 $3$）

所有路径长度都 $\ge 3$，且 $K=3$ 是最大可能值。

数据范围与提示

• $2 \le N \le 10^5$
• 测试点 $2 \ldots 4$：树为星型（至多一个节点度数大于 $2$）
• 测试点 $5 \ldots 8$：$N \le 10^3$
• 测试点 $9 \ldots 15$：无特殊限制