题目描述

给定一个包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

找到最小的整数 $K$，使得可以对每个顶点进行染色，满足以下两个条件。你可以使用任意数量的颜色。

• 对于每个颜色，以该颜色染色的顶点集合是连通的，形成一条简单路径。
• 对于树上的所有简单路径，路径上顶点的不同颜色数最多为 $K$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$N$ $A_1$ $B_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$

输出

输出答案。

示例输入 1

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

示例输出 1

3

如果 $K=3$，则可以通过将顶点 $1,2,3,4,5$ 染成颜色 $1$，顶点 $6$ 染成颜色 $2$，顶点 $7$ 染成颜色 $3$ 来满足条件。如果 $K \leq 2$，没有办法对顶点进行染色满足条件，因此答案为 $3$。

示例输入 2

6
3 5
6 4
6 3
4 2
1 5

示例输出 2

1

示例输入 3

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

示例输出 3

3