Problem Statement

There is a tree with $N$ vertices numbered $1,2,\dots,N$. Here, $N$ is odd.

The edges are also numbered $1,2,\dots,N-1$, and edge $i$ connects vertices $A_i$ and $B_i$.

Each vertex $i$ has a variable $x_i$, and initially $x_i=0$ for every vertex $i$.

Now, for $i=1,2,\dots,N-1$ in this order, perform the following operation.

• First, remove edge $i$. As a result, the tree is split into two connected components.
• For every vertex $v$ in the connected component containing more vertices, add $i$ to $x_v$.
  • Since $N$ is odd, the connected component containing more vertices is uniquely determined.
• Finally, restore edge $i$.

Find the values of the variables $x_1,x_2,\dots,x_N$ of the vertices after all operations are performed.

Constraints

• All input values are integers.
• $N$ is an odd number satisfying $3 \le N \le 2 \times 10^5 - 1$.
• $1 \le A_i < B_i \le N$
• The given graph is a tree.

Input

The input is given from Standard Input in the following format:

• $N$
• $A_1$ $B_1$
• $A_2$ $B_2$
• $\vdots$
• $A_{N-1}$ $B_{N-1}$

Output

Output the final values of the variables in the following format:

• $x_1$ $x_2$ $\dots$ $x_N$

5
2 4
1 5
1 4
1 3

10 6 6 7 8

• For $i=1$, the following operation is performed.
  • Removing edge $1$ splits the tree into a connected component with vertex $2$ and a connected component with vertices $1,3,4,5$.
  • The larger one is the connected component with vertices $1,3,4,5$, so $1$ is added to all of their variables.
  • As a result, the values of the variables become $(x_1,x_2,x_3,x_4,x_5)=(1,0,1,1,1)$.
  • Finally, edge $1$ is restored.
• For $i=2$, the following operation is performed.
  • Removing edge $2$ splits the tree into a connected component with vertex $5$ and a connected component with vertices $1,2,3,4$.
  • The larger one is the connected component with vertices $1,2,3,4$, so $2$ is added to all of their variables.
  • As a result, the values of the variables become $(x_1,x_2,x_3,x_4,x_5)=(3,2,3,3,1)$.
  • Finally, edge $2$ is restored.
• For $i=3$, the following operation is performed.
  • Removing edge $3$ splits the tree into a connected component with vertices $2,4$ and a connected component with vertices $1,3,5$.
  • The larger one is the connected component with vertices $1,3,5$, so $3$ is added to all of their variables.
  • As a result, the values of the variables become $(x_1,x_2,x_3,x_4,x_5)=(6,2,6,3,4)$.
  • Finally, edge $3$ is restored.
• For $i=4$, the following operation is performed.
  • Removing edge $4$ splits the tree into a connected component with vertex $3$ and a connected component with vertices $1,2,4,5$.
  • The larger one is the connected component with vertices $1,2,4,5$, so $4$ is added to all of their variables.
  • As a result, the values of the variables become $(x_1,x_2,x_3,x_4,x_5)=(10,6,6,7,8)$.
  • Finally, edge $4$ is restored.

The final values of the variables are $(x_1,x_2,x_3,x_4,x_5)=(10,6,6,7,8)$.

3
1 2
2 3

2 3 1

9
4 6
2 3
1 5
7 8
2 9
5 6
2 6
7 9

20 36 34 28 23 29 23 19 31

• Source: AtCoder ABC 479 E