{"problem":{"name":"Miracle Tree","description":{"content":"We have a tree with $N$ vertices, numbered $1, 2, \\dots, N$. The $i$\\-th edge $(1 \\leq i \\leq N-1)$ connects Vertex $A_i$ and Vertex $B_i$. A boy E869120 found this tree and wants to write an integer ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc117_d"},"statements":[{"statement_type":"Markdown","content":"We have a tree with $N$ vertices, numbered $1, 2, \\dots, N$. The $i$\\-th edge $(1 \\leq i \\leq N-1)$ connects Vertex $A_i$ and Vertex $B_i$.\nA boy E869120 found this tree and wants to write an integer in each vertex to surprise another boy square1001. For that, the following conditions need to be satisfied, where $E_i$ is the integer written on Vertex $i$.\n\n> **Condition 1:** $E_i \\geq 1$ $(1 \\leq i \\leq N)$ holds.  \n> **Condition 2:** $|E_i - E_j| \\geq dist(i, j)$ holds for every pair $(i, j)$ $(1 \\leq i < j \\leq N)$.  \n> **Condition 3:** the value $\\max(E_1, E_2, \\dots, E_N)$ should be minimized while satisfying Conditions 1 and 2.\n\nHere, $dist(i, j)$ is:\n\n*   the length of the simple path (the path without repetition of the same vertex) from Vertex $i$ to $j$.\n*   In other words, it is the value $L$ where the simple path is $q_0 \\to q_1 \\to q_2 \\to \\cdots \\to q_L$ ($q_0 = i, q_L = j$).\n\nConstruct one way to write integers that surprises square1001.\n\n## Constraints\n\n*   $2 \\leq N \\leq 200000$\n*   $1 \\leq A_i < B_i \\leq N$\n*   The given graph is a tree.\n*   All values in input are integers.\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":"arc117_d","tags":[],"sample_group":[["2\n1 2","2 1\n\nIf we write an integer $2$ on Vertex $1$ and an integer $1$ on Vertex $2$, we have $dist(1, 2) = 1$ and $|E_1 - E_2| = 1$, satisfying Condition 2.\nThe other conditions are also satisfied, so we can surprise square1001 this way.\n$(E_1, E_2) = (1, 2)$ will also be accepted."],["4\n1 2\n1 4\n2 3","3 2 1 4\n\n$(E_1, E_2, E_3, E_4) = (2, 3, 4, 1)$ will also be accepted."]],"created_at":"2026-03-03 11:01:14"}}