問題文

$N$ 頂点の木があり、頂点には $1, 2, \\dots, N$ と番号が振られています。$i$ 番目 $(1 \\leq i \\leq N-1)$ の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。

木を見つけた E869120 君は、$N$ 個の頂点それぞれに整数を書き込み、square1001 君を驚かせようとしています。彼を驚かせるためには、頂点 $i$ に書かれた整数を $E_i$ とするとき、次の条件を満たす必要があります。

条件1　$E_i \\geq 1$ $(1 \\leq i \\leq N)$ を満たす。
条件2　すべての組 $(i, j)$ $(1 \\leq i < j \\leq N)$ について、$|E_i - E_j| \\geq dist(i, j)$ を満たす。
条件3　条件 1・条件 2 を満たす中で、$\\max(E_1, E_2, \\dots, E_N)$ の値が最小になる。

ただし、$dist(i, j)$ は次の値を指します。

• 頂点 $i$ から $j$ への単純パス（同じ頂点を $2$ 度通らない経路）の長さ。
• つまり、単純パスを $q_0 \\to q_1 \\to q_2 \\to \\cdots \\to q_L$（$q_0 = i, q_L = j$）とするときの $L$ の値。

square1001 君を驚かせるような整数の書き方を $1$ つ構成してください。

制約

• $2 \\leq N \\leq 200000$
• $1 \\leq A_i < B_i \\leq N$
• 与えられるグラフは木である
• 入力はすべて整数

入力

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

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\\vdots$ $A_{N-1}$ $B_{N-1}$

出力

木に書き込む整数 $E_1, E_2, \\cdots, E_N$ を順に、空白で区切って $1$ 行で出力してください。

問題文の条件を満たす整数の書き込み方が複数存在する場合は、どれを出力しても正解となります。

$E_1$ $E_2$ $\\cdots$ $E_{N}$

入力例 1

2
1 2

出力例 1

2 1

頂点 $1$ に整数 $2$ を、頂点 $2$ に整数 $1$ を書き込んだ場合、$dist(1, 2) = 1$、$|E_1 - E_2| = 1$ であるため、問題文中の条件 2 を満たします。

その他の条件もすべて満たすため、この書き込み方は square1001 君を驚かせることができます。

他にも、$(E_1, E_2) = (1, 2)$ は正解となります。

入力例 2

4
1 2
1 4
2 3

出力例 2

3 2 1 4

他にも、$(E_1, E_2, E_3, E_4) = (2, 3, 4, 1)$ は正解となります。