問題文

$N$頂点の根付き木があります。
根付き木の頂点には$1$から$N$の番号がついており、根は頂点$1$です。また、$i(1\le 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$
$⋮$
$v_{N-1}{w}_{N-1}$

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

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

出力

$N$行出力してください。
$i(1\le i\le 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