{"raw_statement":[{"iden":"problem statement","content":"You are given a tree with $N$ vertices numbered $1$ through $N$. The $i$\\-th edge connects vertex $A_i$ and vertex $B_i$.\nFind the minimum integer $K$ such that you can paint each vertex in a color so that the following two conditions are satisfied. You may use any number of colors.\n\n*   For each color, the set of vertices painted in the color is connected and forms a simple path.\n*   For all simple paths on the tree, there are at most $K$ distinct colors of the vertices in the path."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i, B_i \\leq N$\n*   The given graph is a tree.\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$"},{"iden":"sample input 1","content":"7\n3 4\n1 5\n4 5\n1 2\n7 4\n1 6"},{"iden":"sample output 1","content":"3\n\nIf $K=3$, the conditions can be satisfied by painting vertices $1,2,3,4$, and $5$ in color $1$, vertex $6$ in color $2$, and vertex $7$ in color $3$. If $K \\leq 2$, there is no way to paint the vertices to satisfy the conditions, so the answer is $3$."},{"iden":"sample input 2","content":"6\n3 5\n6 4\n6 3\n4 2\n1 5"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"9\n1 3\n9 5\n8 7\n2 1\n5 2\n5 8\n4 8\n6 1"},{"iden":"sample output 3","content":"3"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}