题目描述

给定一棵具有 $N$ 个顶点的树。顶点编号为 $1,2,\\ldots ,N$，第 $i$ 条边是一条连接顶点 $u_i$ 和顶点 $v_i$ 的无向边。

对于每个整数 $i\\,(1 \\leq i \\leq N)$，找到 $\\sum_{j=1}^{N}dis(i,j)$。

这里，$dis(i,j)$ 表示从顶点 $i$ 到顶点 $j$ 所需经过的最小边数。

约束条件

• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq u_i < v_i \\leq N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入

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

$N$ $u_1$ $v_1$ $u_2$ $v_2$ $\\vdots$ $u_{N-1}$ $v_{N-1}$

输出

输出 $N$ 行。

第 $i$ 行应该包含 $\\sum_{j=1}^{N}dis(i,j)$。

示例输入 1

3
1 2
2 3

示例输出 1

3
2
3

我们有：

$dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3$,

$dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2$,

$dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3$.

示例输入 2

2
1 2

示例输出 2

1
1

示例输入 3

6
1 6
1 5
1 3
1 4
1 2

示例输出 3

5
9
9
9
9
9