AT_ttpc2024_2_g Coloring Tree

$ N $ 頂点からなる根付き木が与えられます。この木の頂点には $ 1 $ から $ N $ までの番号が振られており、頂点 $ 1 $ が根です。 $ i $ 番目の辺は、頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 木の各頂点に対し、次の条件を満たすように色を塗ります。 - 頂点 $ i $ の色を $ c_i $ とする。任意の相異なる $ 3 $ 頂点 $ u, v, w $ について、「 $ w = \mathrm{lca}(u, v) $ かつ $ c_u = c_v $ ならば $ c_u \neq c_w $ 」 が成り立つ。 このとき、使用した色の種類数としてありうる最小値を求めてください。 ここで、 $ \mathrm{lca}(u, v) $ は頂点 $ u $ と頂点 $ v $ の最小共通祖先を表します。

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

答えを出力せよ。

### Sample Explanation 1 例えば、下図のように色を塗ると、与えられた条件を満たします。 $ 2 $ 色以下で条件を満たすように頂点を塗り分ける方法は存在しないため、使う色の種類数の最小値は $ 3 $ となります。  ### Constraints - 入力はすべて整数 - $ 3