题目描述

给定一个包含 $N$ 个顶点的树结构。顶点编号为 $1$ 到 $N$，其中第 $i$ 条边连接顶点 $u_i$ 和 $v_i$ 的无向边。

对于每个整数 $i(1 \leq i \leq N)$，请计算 $\sum_{j=1}^{N}dis(i,j)$ 的值。

其中 $dis(i,j)$ 表示顶点 $i$ 到顶点 $j$ 的最短路径所经过的边数。

输入格式

输入数据格式如下：

$N$

$u_1$ $v_1$

$u₂$ $v₂$

$\dots$

$u_{N-1}$ $v_{N-1}$

输出格式

输出 $N$ 行结果，第 $i$ 行对应顶点 $i$ 的距离总和。

输入输出样例

样例1输入：

3
1 2
2 3

样例1输出：

3
2
3

解释：

• 顶点1：$0+1+2=3$
• 顶点2：$1+0+1=2$
• 顶点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

数据范围

• $2 \leq N \leq 2×10^5$
• $1 \leq u_i < v_i \leq N$
• 保证输入构成一棵树
• 所有输入均为整数