C - ThREE

Contest Duration: 2020-03-08(Sun) 12:00 - 2020-03-08(Sun) 14:00 (local time) (120 minutes) Back to Home

C - ThREE Editorial

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$ つ見つけてください。

入力は以下の形式で標準入力から与えられる。

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

問題の条件を満たす順列が存在しない場合は -1 と $1$ 行に出力せよ。

存在する場合、条件を満たす順列の $1$ つを空白区切りで $1$ 行に出力せよ。

Copy

Copy

1 2 5 4 3

距離が $3$ である頂点の組は $(2, 4)$ と $(2, 5)$ の $2$ つです。

であるため、この順列は条件を満たします。

Score : $600$ points

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.

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

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.

Copy

Copy

1 2 5 4 3

The distance between two vertices is $3$ for the two pairs $(2, 4)$ and $(2, 5)$ .

Thus, this permutation satisfies the condition.