AT_hitachi2020_c.ThREE

有一棵包含 $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$ 的最短路径所经过的边数。

请为高桥君找到一个满足条件的排列。

输入以如下格式从标准输入读入。

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

如果不存在满足条件的排列，则输出 $-1$，占一行。

如果存在，输出任意一个满足条件的排列，空格分隔，输出一行。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• 给定的图是一棵树

样例解释 1

距离为 $3$ 的顶点对有 $(2,\ 4)$ 和 $(2,\ 5)$ 这两组。

• $p_2 + p_4 = 6$
• $p_2 \times p_5 = 6$
  因此，这个排列满足条件。

由 ChatGPT 4.1 翻译