题目描述

$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$ つ見つけてください。

输入格式

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

$N$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_{N-1}$ $b_{N-1}$

输出格式

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

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

题目大意

给定一棵树，要求构造一个排列 $P$，满足以下条件：

• 对树上的每一对点 $(i,j)$，如果这两个点之间的距离为 $3$，则 $p_i\times p_j$ 和 $p_i+p_j$ 中至少一个为 $3$ 的倍数。

树上每一条边的长度为 $1$。

5
1 2
1 3
3 4
3 5

1 2 5 4 3

提示

制約

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

Sample Explanation 1

距離が $3$ である頂点の組は $(2,\ 4)$ と $(2,\ 5)$ の $2$ つです。 - $p_2\ +\ p_4\ =\ 6$ - $p_2\times\ p_5\ =\ 6$ であるため、この順列は条件を満たします。