問題文

$N$頂点の根付き木があります。
根付き木の頂点には$1$から$N$の番号がついており、根は頂点$1$です。また、$i (1 \leq i < N)$番目の辺は頂点$v_i$と頂点$w_i$を双方向に結んでいます。
$k=1,2,\cdots,N$について、以下の問題を解いてください。

• 木の2頂点の組$(v,w)$で、それらの最近共通祖先(LCA)が頂点$k$であるようなものの個数を求めよ。

入力

$N$
$v_1 \ w_1$
$v_2 \ w_2$
$\vdots$
$v_{N-1} \ w_{N-1}$

入力は以下の制約を満たします。

• 入力はすべて整数
• $1 \leq N \leq 2\times10^5$
• $1 \leq v_i, w_i \leq N (1 \leq i < N)$
• 与えられたグラフは木である

出力

$N$行出力してください。
$i (1 \leq i \leq N)$行目には、$k=i$のときの答えを出力してください。

サンプル

3
1 2
1 3

7
1
1

5
1 2
2 3
3 4
3 5

9
7
7
1
1

1

1