AT_hitachi2020_c ThREE

[problemUrl]: https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_c $ 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

N/A

### 制約 - $ 2\leq\ N\leq\ 2\times\ 10^5 $ - $ 1\leq\ a_i,\ b_i\ \leq\ N $ - 与えられるグラフは木である ### Sample Explanation 1 距離が $ 3 $ である頂点の組は $ (2,\ 4) $ と $ (2,\ 5) $ の $ 2 $ つです。 - $ p_2\ +\ p_4\ =\ 6 $ - $ p_2\times\ p_5\ =\ 6 $ であるため、この順列は条件を満たします。