AT_ttpc2024_2_g Coloring Tree

You are given a rooted tree with $ N $ vertices. The vertices are numbered from $ 1 $ to $ N $ , with vertex $ 1 $ being the root. The $ i $ -th edge connects vertex $ A_i $ and vertex $ B_i $ . Assign a color to each vertex such that the following condition is satisfied: - Let the color of vertex $ i $ be $ c_i $ . For any three distinct vertices $ u $ , $ v $ , and $ w $ , if $ w = \mathrm{lca}(u, v) $ and $ c_u = c_v $ , then $ c_u \neq c_w $ . Find the minimum possible number of distinct colors used. Here, $ \mathrm{lca}(u, v) $ denotes the lowest common ancestor of vertices $ u $ and $ v $ .

The input is given in the following format: > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

Print the minimum number of distinct colors required.

### Sample Explanation 1 For example, the coloring shown below satisfies the given conditions. Since there is no way to satisfy the conditions using two or fewer colors, the minimum number of colors needed is $ 3 $ .  ### Constraints - All input values are integers. - $ 3 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i, B_i \leq N $ - The input graph is a tree.