問題文

1 から N までの番号がつけられた N 個の頂点を持つ木があります。 この木の i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

この木に対し、頂点 r を根としたときの転倒数を以下のように定義します。

• 頂点 r から頂点 u の単純パスの端点または辺上に頂点 v が含まれるような組 (u, v) \ (u \lt v) の個数

1 以上 N 以下の全ての整数 r に対し、頂点 r を根としたときの転倒数を求めてください。

制約

• 入力は全て整数
• 2 \leq N \leq 10^{5}
• 1 \leq A_i, B_i \leq N
• 与えられるグラフは木である。

入力例 1

3
1 3
2 3

出力例 1

1
2
2

• 頂点 1 を根としたときの転倒数は、(u, v) = (2, 3) より 1 です
• 頂点 2 を根としたときの転倒数は、(u, v) = (1, 2), (1, 3) より 2 です
• 頂点 3 を根としたときの転倒数は、(u, v) = (1, 3), (2, 3) より 2 です。

入力例 2

7
1 4
1 6
2 4
2 5
3 4
4 7

出力例 2

2
3
4
3
7
7
9