{"problem":{"name":"Coloring Tree","description":{"content":"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 eac","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_2_g"},"statements":[{"statement_type":"Markdown","content":"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$.\nAssign a color to each vertex such that the following condition is satisfied:\n\n*   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$.\n\nFind the minimum possible number of distinct colors used.\nHere, $\\mathrm{lca}(u, v)$ denotes the lowest common ancestor of vertices $u$ and $v$.\n\n## Constraints\n\n*   All input values are integers.\n*   $3 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i, B_i \\leq N$\n*   The input graph is a tree.\n\n## Input\n\nThe input is given in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_2_g","tags":[],"sample_group":[["8\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n6 8","3\n\nFor example, the coloring shown below satisfies the given conditions.\nSince there is no way to satisfy the conditions using two or fewer colors, the minimum number of colors needed is $3$.\n![image](https://img.atcoder.jp/ttpc2024_2/956692bccf77f0df9d83837f5a7e95cb.svg)"],["4\n1 2\n2 3\n3 4","1"]],"created_at":"2026-03-03 11:01:14"}}