题目描述

$N$ 頂点の木が与えられます。頂点には $1$ から $N$ までの番号がついており、$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。

各頂点に以下の条件を満たすように色を塗ることができる整数 $K$ の最小値を求めてください。ただし、使える色の種類数に制限はありません。

• 各色について、その色で塗られた頂点の集合は連結で単純パスをなす
• 任意の木上の単純パスについて、そのパス内に含まれる頂点に塗られた色の種類数は $K$ 以下

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定一个 $n$ 个点的树，你可以将树划分为若干条不交的路径，每条路径染一种颜色。

找到最小的 $K$ 满足：对于任意一条原树上的路径，其经过的颜色数不超过 $K$。

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

3

6
3 5
6 4
6 3
4 2
1 5

1

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

3

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i,\ B_i\ \leq\ N$
• 与えられるグラフは木
• 入力はすべて整数

Sample Explanation 1

$K\ =\ 3$ のとき、頂点 $1,2,3,4,5$ を色 $1$、頂点 $6$ を色 $2$、頂点 $7$ を色 $3$ で塗るなどの方法で条件を満たすことができます。 $K\ \leq\ 2$ とすると条件を満たす色の塗り方は存在しないので答えは $3$ です。