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: n, *L = map(int, open(0).read().split())
  g = [[] for _ in range(n)]
  for a, b in zip(*[iter(L)] * 2):
      g[a - 1].append(b - 1)
      g[b - 1].append(a - 1)
  tr = [-1] * n
  q = [0]
  tr[0] = 0
  while q:
      cu = q.pop()
      for nx in g[cu]:
          if tr[nx] < 0:
              tr[nx] = 1 - tr[cu]
              q.append(nx)
  lab = [-1] * n
  z, o = map(tr.count, (0, 1))
  if z <= n // 3 or o <= n // 3:
      f = 0 if z <= n // 3 else 1
      onetwo = 1
      thr = 3
      for i, x in enumerate(tr):
          if x == f:
              lab[i] = thr
              thr += 3
      for i, x in enumerate(tr):
          if x == 1 - f:
              if thr <= n:
                  lab[i] = thr
                  thr += 3
              else:
                  lab[i] = onetwo
                  onetwo += 1 if onetwo % 3 == 1 else 2
  else:
      one = 1
      for i, x in enumerate(tr):
          if x == 0:
              lab[i] = one
              one += 3
              if one > n:
                  break
      two = 2
      for i, x in enumerate(tr):
          if x == 1:
              lab[i] = two
              two += 3
              if two > n:
                  break
      thr = 3
      for i in range(n):
          if lab[i] < 0:
              lab[i] = thr
              thr += 3
  print(*lab)
  
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."}]