問題文

N 頂点の木が与えられます。i 番目の辺は長さが 1 で、頂点 u_i と頂点 v_i を結んでいます。

頂点 1 を出発し、全ての辺を 2 回ずつ通り、頂点 1 に戻ってくる移動方法を考えます。

i 番目の要素が i 番目に通った頂点の深さと定義される数列としてありうる辞書順最小のものを求めてください。ただし、頂点の深さとは頂点 1 との距離を指すとします。

制約

• 2 \leq N \leq 2\times 10^5
• 1 \leq u_i < v_i \leq N
• 与えられるグラフは木
• 入力はすべて整数

入力例 1

4
1 2
2 3
1 4

出力例 1

0 1 0 1 2 1 0

頂点 1 →頂点 4 →頂点 1 →頂点 2 →頂点 3 →頂点 2 →頂点 1 の順に通った場合、深さを並べた数列が辞書順最小となります。

入力例 2

2
1 2

出力例 2

0 1 0

入力例 3

6
2 5
3 5
1 4
4 5
4 6

出力例 3

0 1 2 1 2 3 2 3 2 1 0