/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
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 つ見つけてください。
制約
- 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 行に出力せよ。
存在する場合、条件を満たす順列の 1 つを空白区切りで 1 行に出力せよ。
入力例 1
5 1 2 1 3 3 4 3 5
出力例 1
1 2 5 4 3
距離が 3 である頂点の組は (2, 4) と (2, 5) の 2 つです。
- p_2 + p_4 = 6
- p_2\times p_5 = 6
であるため、この順列は条件を満たします。
Score : 600 points
Problem Statement
We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.
Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:
- For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.
Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.
Help Takahashi by finding a permutation that satisfies the condition.
Constraints
- 2\leq N\leq 2\times 10^5
- 1\leq a_i, b_i \leq N
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}
Output
If no permutation satisfies the condition, print -1.
Otherwise, print a permutation satisfying the condition, with space in between. If there are multiple solutions, you can print any of them.
Sample Input 1
5 1 2 1 3 3 4 3 5
Sample Output 1
1 2 5 4 3
The distance between two vertices is 3 for the two pairs (2, 4) and (2, 5).
- p_2 + p_4 = 6
- p_2\times p_5 = 6
Thus, this permutation satisfies the condition.