FJ 的 $N$ ($2\le N\le 2\cdot 10^5$) 头奶牛（编号为 $1\dots N$）之间最初有 $N-1$ 对朋友关系，构成一棵树。奶牛们将陆续离开农场去度假。在第 $i$ 天，第 $i$ 头奶牛离开农场，随后第 $i$ 头奶牛的所有仍在农场的朋友之间会建立朋友关系。

对于从 $1$ 到 $N$ 的每个 $i$，在第 $i$ 头奶牛离开之前，有多少个由不同奶牛组成的有序三元组 $(a,b,c)$，满足 $a,b,c$ 均未去度假，$a$ 与 $b$ 是朋友，$b$ 与 $c$ 是朋友？

输入格式

第一行包含 $N$。

接下来的 $N-1$ 行包含两个整数 $u_i$ 和 $v_i$，表示奶牛 $u_i$ 和 $v_i$ 最初是朋友 ($1\le u_i,v_i\le N$)。

输出格式

对于从 $1$ 到 $N$ 的每个 $i$，在单独的行中输出答案。

样例

输入格式 1

3
1 2
2 3

输出格式 1

2
0
0

说明

在第 $1$ 头奶牛离开前，三元组为 $(1,2,3)$ 和 $(3,2,1)$。 在第 $1$ 头奶牛离开后，剩余奶牛不足 $3$ 头，因此不存在三元组。

输入格式 2

4
1 2
1 3
1 4

输出格式 2

6
6
0
0

说明

最初，第 $1$ 头奶牛与所有其他奶牛是朋友，且没有其他奶牛互为朋友，因此三元组为 $(a, 1, c)$，其中 $a, c$ 是 $\{2, 3, 4\}$ 中不同的奶牛，共有 $3 \cdot 2 = 6$ 个三元组。 在第 $1$ 头奶牛离开后，剩余的三头奶牛互为朋友，因此三元组为这三头奶牛的任意 $3! = 6$ 种排列。 在第 $2$ 头奶牛离开后，剩余奶牛不足 $3$ 头，因此不存在三元组。

输入格式 3

5
3 5
5 1
1 4
1 2

输出格式 3

8
10
2
0
0

SCORING

• 测试点 4-5：$N\le 500$
• 测试点 6-10：$N\le 5000$
• 测试点 11-20：无附加限制。