配点 : $600$ 点

問題文

$N$ 頂点の木があります。頂点には $1$ から $N$ までの番号がついており、 $i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

$3$ が大好きな高橋くんは、以下の条件を満たす $1$ から $N$ までの整数の順列 $p_1, p_2, \ldots , p_N$ を探しています。

• すべての頂点の組 $(i, j)$ について、頂点 $i$ と頂点 $j$ の距離が $3$ であるならば、$p_i$ と $p_j$ の和または積が $3$ の倍数である。

ただし、頂点 $i$ と頂点 $j$ の距離とは、頂点 $i$ から頂点 $j$ へ最短経路で移動するときに使用する辺の個数のことを指します。

高橋くんのために条件を満たす順列を $1$ つ見つけてください。

制約

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

入力

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

$N$

$a_1$ $b_1$

$a_2$ $b_2$

$\vdots$

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

出力

問題の条件を満たす順列が存在しない場合は -1 と $1$ 行に出力せよ。

存在する場合、条件を満たす順列の $1$ つを空白区切りで $1$ 行に出力せよ。

5
1 2
1 3
3 4
3 5

1 2 5 4 3

距離が $3$ である頂点の組は $(2, 4)$ と $(2, 5)$ の $2$ つです。

• $p_2 + p_4 = 6$
• $p_2\times p_5 = 6$

であるため、この順列は条件を満たします。