{"raw_statement":[{"iden":"problem statement","content":"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$.\nTakahashi 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:\n\n*   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$.\n\nHere the distance between Vertex $i$ and Vertex $j$ is the number of edges contained in the shortest path from Vertex $i$ to Vertex $j$.\nHelp Takahashi by finding a permutation that satisfies the condition."},{"iden":"constraints","content":"*   $2\\leq N\\leq 2\\times 10^5$\n*   $1\\leq a_i, b_i \\leq N$\n*   The given graph is a tree."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$\\vdots$\n$a_{N-1}$ $b_{N-1}$"},{"iden":"sample input 1","content":"5\n1 2\n1 3\n3 4\n3 5"},{"iden":"sample output 1","content":"1 2 5 4 3 \n\nThe distance between two vertices is $3$ for the two pairs $(2, 4)$ and $(2, 5)$.\n\n*   $p_2 + p_4 = 6$\n*   $p_2\\times p_5 = 6$\n\nThus, this permutation satisfies the condition."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}