AT_abc479_e.Cut and Add

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.

有一棵包含 $N$ 个顶点的树，顶点编号为 $1,2,\dots,N$。其中 $N$ 为奇数。
树的边也编号为 $1,2,\dots,N-1$，第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

每个顶点 $i$ 上有一个变量 $x_i$，初始时对所有顶点 $i$ 均有 $x_i = 0$。

接下来，按 $i = 1,2,\dots,N-1$ 的顺序依次执行以下操作：

• 首先，删除第 $i$ 条边。此时树被分割为两个连通分量。
• 对于包含更多顶点的那个连通分量中的每个顶点 $v$，将 $i$ 加到 $x_v$ 上。
  • 由于 $N$ 是奇数，包含更多顶点的连通分量是唯一确定的。
• 最后，恢复第 $i$ 条边。

在完成所有操作后，求各顶点的变量值 $x_1,x_2,\dots,x_N$。

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}$

输入从标准输入中按以下格式给出：

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

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

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

以如下格式输出变量的最终值：

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

Sample 1 Explanation:

• 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)$.

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.

样例 1 解释：

• 对于 $i=1$，执行以下操作：
  • 删除边 $1$ 将树分割为两个连通分量：一个包含顶点 $2$，另一个包含顶点 $1,3,4,5$。
  • 较大的连通分量是包含顶点 $1,3,4,5$ 的那个，因此将 $1$ 加到这些顶点对应的变量上。
  • 此时各变量的值变为 $(x_1,x_2,x_3,x_4,x_5)=(1,0,1,1,1)$。
  • 最后，恢复边 $1$。
• 对于 $i=2$，执行以下操作：
  • 删除边 $2$ 将树分割为两个连通分量：一个包含顶点 $5$，另一个包含顶点 $1,2,3,4$。
  • 较大的连通分量是包含顶点 $1,2,3,4$ 的那个，因此将 $2$ 加到这些顶点对应的变量上。
  • 此时各变量的值变为 $(x_1,x_2,x_3,x_4,x_5)=(3,2,3,3,1)$。
  • 最后，恢复边 $2$。
• 对于 $i=3$，执行以下操作：
  • 删除边 $3$ 将树分割为两个连通分量：一个包含顶点 $2,4$，另一个包含顶点 $1,3,5$。
  • 较大的连通分量是包含顶点 $1,3,5$ 的那个，因此将 $3$ 加到这些顶点对应的变量上。
  • 此时各变量的值变为 $(x_1,x_2,x_3,x_4,x_5)=(6,2,6,3,4)$。
  • 最后，恢复边 $3$。
• 对于 $i=4$，执行以下操作：
  • 删除边 $4$ 将树分割为两个连通分量：一个包含顶点 $3$，另一个包含顶点 $1,2,4,5$。
  • 较大的连通分量是包含顶点 $1,2,4,5$ 的那个，因此将 $4$ 加到这些顶点对应的变量上。
  • 此时各变量的值变为 $(x_1,x_2,x_3,x_4,x_5)=(10,6,6,7,8)$。
  • 最后，恢复边 $4$。

最终各变量的值为 $(x_1,x_2,x_3,x_4,x_5)=(10,6,6,7,8)$。

约束条件

• 所有输入值均为整数。
• $N$ 是满足 $3 \le N \le 2 \times 10^5 - 1$ 的奇数。
• $1 \le A_i < B_i \le N$。
• 给定图是一棵树。