{"problem":{"name":"Coloring Edges on Tree","description":{"content":"Given is a tree $G$ with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$. Consider painting the edges in $G$ with some number of co","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc146_d"},"statements":[{"statement_type":"Markdown","content":"Given is a tree $G$ with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$.\nConsider painting the edges in $G$ with some number of colors. We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.\nAmong the colorings satisfying the condition above, construct one that uses the minimum number of colors.\n\n## Constraints\n\n*   $2 \\le N \\le 10^5$\n*   $1 \\le a_i \\lt b_i \\le N$\n*   All values in input are integers.\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input 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":"abc146_d","tags":[],"sample_group":[["3\n1 2\n2 3","2\n1\n2"],["8\n1 2\n2 3\n2 4\n2 5\n4 7\n5 6\n6 8","4\n1\n2\n3\n4\n1\n1\n2"],["6\n1 2\n1 3\n1 4\n1 5\n1 6","5\n1\n2\n3\n4\n5"]],"created_at":"2026-03-03 11:01:14"}}