题目描述

有一棵包含 $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$ 的值。

输入格式

输入按以下格式从标准输入读入：

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

输出格式

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

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

5
2 4
1 5
1 4
1 3

10 6 6 7 8

• 对于 $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)$。

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

数据范围

• 输入中的所有值均为整数。

• $N$ 是满足 $3 \le N \le 2 \times 10^5 - 1$ 的奇数。

• $1 \le A_i < B_i \le N$

• 给定的图是一棵树。

• 来源：AtCoder ABC 479 E

子任务设置

• 子任务 1（30 分）：$N \le 2000$。
• 子任务 2（30 分）：$N \le 50000$。
• 子任务 3（40 分）：无特殊限制。