← 返回题目列表

AtCoder · hitachi2020_c

C. 三

中文机器翻译题面 查看原题

分数: 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

因此,该排列满足条件。