{"problem":{"name":"ThREE","description":{"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$. Takahashi loves the number $3$. He is seeking a permutation $p_1, p","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"hitachi2020_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $2\\leq N\\leq 2\\times 10^5$\n*   $1\\leq a_i, b_i \\leq N$\n*   The given graph is a tree.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"hitachi2020_c","tags":[],"sample_group":[["5\n1 2\n1 3\n3 4\n3 5","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."]],"created_at":"2026-03-03 11:01:14"}}