配点 : $1200$ 点

問題文

高橋君の会社は $N$ 個の部屋からなり、各部屋には $1$ から $N$ の番号が割り振られています。 また、$N-1$ 本の通路があり、$i$ 番目の通路は部屋 $a_i$ と部屋 $b_i$ を繋いでいます。 どの $2$ つの部屋の間もこれらの通路のみを通って移動できることが分かっています。

今高橋君はある部屋に迷い込んでしまいました。この部屋を $r$ とします。 そこで、高橋君は自分の部屋である部屋 $1$ に戻るために、以下の方法で移動することを繰り返すことにしました。

• 今まで訪れた部屋に隣接する部屋の中でまだ訪れていない部屋の内、番号が一番小さい部屋に移動する。

部屋 $1$ に戻るまでに行う必要のある移動の回数を $c_r$ とします。 $c_2,c_3,...,c_N$ をすべて求めてください。 ただし、$1$ 回の移動でいくつの通路を通るとしても、移動は $1$ 回として数えられることに注意してください。

制約

• $2 \leq N \leq 2\times 10^5$
• $1 \leq a_i,b_i \leq N$
• $a_i \neq b_i$
• 入力で与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $b_1$

$:$

$a_{N-1}$ $b_{N-1}$

出力

各 $r$ に対して $c_r$ を以下の形式に従って出力せよ。

$c_2$ $c_3$ $...$ $c_N$

6
1 5
5 6
6 2
6 3
6 4

5 5 5 1 5

例えば部屋 $2$ に迷い込んでいた場合、高橋君は以下のように移動します。

• 部屋 $6$ に移動する。
• 部屋 $3$ に移動する。
• 部屋 $4$ に移動する。
• 部屋 $5$ に移動する。
• 部屋 $1$ に移動する。

6
1 2
2 3
3 4
4 5
5 6

1 2 3 4 5

10
1 5
5 6
6 10
6 4
10 3
10 8
8 2
4 7
4 9

7 5 3 1 3 4 7 4 5