问题描述

我们有一个包含 $N$ 个顶点的树。顶点从 $1$ 到 $N$ 编号，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

Takahashi 喜欢数字 $3$。他正在寻找一个由整数 $1$ 到 $N$ 组成的排列 $p_1, p_2, \\ldots , p_N$，满足以下条件：

• 对于每一对顶点 $(i, j)$，如果顶点 $i$ 和顶点 $j$ 之间的距离为 $3$，则 $p_i$ 和 $p_j$ 的和或积是 $3$ 的倍数。

这里顶点 $i$ 和顶点 $j$ 之间的距离是从顶点 $i$ 到顶点 $j$ 的最短路径中包含的边数。

帮助 Takahashi 找到满足条件的排列。

约束条件

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

5
1 2
1 3
3 4
3 5

示例输出 1

1 2 5 4 3 

对于两对顶点 $(2, 4)$ 和 $(2, 5)$，它们之间的距离为 $3$。

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

因此，这个排列满足条件。