{"raw_statement":[{"iden":"problem statement","content":"You are given a tree $T$ with $N$ vertices. The $i$\\-th edge connects vertices $A_i$ and $B_i$.\nConstruct an $N$\\-vertex rooted tree $R$ that satisfies the following conditions.\n\n*   For all integer pairs $(x,y)$ such that $1 \\leq x < y \\leq N$,\n    *   if the lowest common ancestor in $R$ of vertices $x$ and $y$ is vertex $z$, then vertex $z$ in $T$ is on the simple path between vertices $x$ and $y$.\n*   In $R$, for all vertices $v$ except for the root, the number of vertices of the subtree rooted at $v$, multiplied by $2$, does not exceed the number of vertices of the subtree rooted at the parent of $v$.\n\nWe can prove that such a rooted tree always exists."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $1\\leq A_i,B_i \\leq N$\n*   All values in the input are integers.\n*   The given graph is a tree."},{"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":"4\n1 2\n2 3\n3 4"},{"iden":"sample output 1","content":"2 -1 4 2\n\nFor example, the lowest common ancestor in $R$ of vertices $1$ and $3$ is vertex $2$; in $T$, vertex $2$ is on the simple path between vertices $1$ and $3$.  \nAlso, for example, in $R$, the subtree rooted at vertex $4$ has two vertices, and the number multiplied by two does not exceed the number of vertices of the subtree rooted at vertex $2$, which has $4$ vertices.\n![image](https://img.atcoder.jp/abc291/7c68a1da41dbfff60a08aad4fe182376.png)"},{"iden":"sample input 2","content":"5\n1 2\n1 3\n1 4\n1 5"},{"iden":"sample output 2","content":"\\-1 1 1 1 1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}