output_description: 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.
  
  * * *
input_description: 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}
attempt: import sys
  
  input = sys.stdin.readline
  
  n = int(input())
  ab = [tuple(map(int, input().split())) for _ in range(n - 1)]
  
  edges = {}
  for i in range(1, n + 1):
      edges[i] = set()
  
  for tmp in ab:
      a, b = tmp
      edges[a].add(b)
      edges[b].add(a)
  
  group = [[], []]
  g_flag = 0
  next = {1}
  while len(next) > 0:
      tmp = list(next)
      next = set()
      for i in tmp:
          group[g_flag].append(i)
          for j in edges[i]:
              next.add(j)
              edges[j].remove(i)
      g_flag = 1 - g_flag
  
  even_n = len(group[0])
  odd_n = len(group[1])
  
  ans = [0] * (n + 1)
  if (even_n > n // 3) & (odd_n > n // 3):
      g1 = group[0][: (n + 2) // 3]
      g2 = group[1][: (n + 1) // 3]
      g0 = group[0][(n + 2) // 3 :] + group[1][(n + 1) // 3 :]
  elif even_n <= n // 3:
      g0 = group[0].extend(group[1][: n // 3 - even_n])
      g1 = group[1][n // 3 - even_n : (n // 3 - even_n) + (n + 2) // 3]
      g2 = group[1][(n // 3 - even_n) + (n + 2) // 3 :]
  else:
      g0 = group[1].extend(group[0][: n // 3 - odd_n])
      g1 = group[1][n // 3 - odd_n : (n // 3 - odd_n) + (n + 2) // 3]
      g2 = group[1][(n // 3 - odd_n) + (n + 2) // 3 :]
  
  # print(group)
  # print(g0)
  # print(g1)
  # print(g2)
  
  for i in range((n + 2) // 3):
      ans[g1[i]] = i * 3 + 1
  for i in range((n + 1) // 3):
      ans[g2[i]] = i * 3 + 2
  for i, val in enumerate(g0):
      ans[val] = (i + 1) * 3
  
  print(" ".join(map(str, ans[1:])))
  
problem_description: 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.
samples: [{"input": "5\n    1 2\n    1 3\n    3 4\n    3 5", "output": "1 2 5 4 3 \n    \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."}]