[ABC293Ex] Optimal Path Decomposition

给定一个 $n$ 个点的树，你可以将树划分为若干条不交的路径，每条路径染一种颜色。 找到最小的 $K$ 满足：对于任意一条原树上的路径，其经过的颜色数不超过 $K$。

[problemUrl]: https://atcoder.jp/contests/abc293/tasks/abc293_h $ N $ 頂点の木が与えられます。頂点には $ 1 $ から $ N $ までの番号がついており、$ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 各頂点に以下の条件を満たすように色を塗ることができる整数 $ K $ の最小値を求めてください。ただし、使える色の種類数に制限はありません。 - 各色について、その色で塗られた頂点の集合は連結で単純パスをなす - 任意の木上の単純パスについて、そのパス内に含まれる頂点に塗られた色の種類数は $ K $ 以下

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

答えを出力せよ。

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 $ です。