分数: 600 点
问题陈述
我们有一棵树 N 顶点。顶点已编号 1 to N,以及 i第一条边连接顶点 a_i 和顶点 b_i.
高桥喜欢这个数字 3。他正在寻求一种排列 p_1, p_2, \ldots , p_N 的整数来自 1 to N 满足以下条件:
- 对于每对顶点 (i, j),如果顶点之间的距离 i 和顶点 j is 3,总和或乘积 p_i 和 p_j 是的倍数 3.
这里是顶点之间的距离 i 和顶点 j 是从顶点开始的最短路径中包含的边数 i 到顶点 j.
帮助高桥找到满足条件的排列。
约束
- 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
两个顶点之间的距离是 3 为两对 (2, 4) 和 (2, 5).
- p_2 + p_4 = 6
- p_2\times p_5 = 6
因此,该排列满足条件。