题目描述

石老板被解体后，他的身体分成了 $n$ 块，并且形成了一棵树。

拥有五彩斑斓灵魂的他，想要对自己的每块身体进行染色，并且希望代价尽可能的小。

具体地，他要选择一个节点 $r$，然后：

• 设一个数组 $d$，$d_i$ 表示 $r$ 点到 $i$ 点的距离。
• 并把所有节点都染个色。

但染色必须要满足两个条件：

• 对于任意被染了相同颜色的点对 $(x,y)$，从点 $x$ 到点 $y$ 的路径上所有点（包括点 $x$ 和点 $y$）的颜色都一样。
• 对于任意被染了相同颜色的点对 $(x,y)$，条件 $d_x \not= d_y$ 必须都满足。

现在，定义一个染色方案的代价为一种颜色的最小出现次数，即 $\min\{\text{cnt}_i\}$。

现在，他让你选择一个最优的节点 $r$，使得染色方案的最小代价最大，输出这个代价。

输入格式

第一行一个整数 $n$ 表示结点个数。

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

输出格式

输出一行一个整数表示最小代价的最大值。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

6
1 2
1 3
1 4
4 5
1 6

样例输出 #2

1

提示

样例 $1$ 如图所示，选 $6$ 号点为根， $5,6,7$ 一种颜色，$1,2,3,4$ 一种颜色。

数据规模与约定

对于 $30\%的数据$，$n \le 2000$。

对于 $100\%$ 的数据， $n\le 200000$， $1\le u,v \le n$，保证数据是一棵树。