配点: $600$ 点

問題文

$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}$

2
1 2

2 1

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

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

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

4
1 2
1 4
2 3

3 2 1 4

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