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
  
  
  def part(s, links):
      grp = [set(), set()]
      q = [(s, -1, 0)]
      while q:
          v, p, g = q.pop()
          grp[g].add(v)
          for u in links[v]:
              if u == p:
                  continue
              q.append((u, v, g ^ 1))
      return grp
  
  
  def solve(n, links):
      grp = part(0, links)
      can = [[], [], []]
      for i in range(1, n + 1):
          can[i % 3].append(i)
      # print(grp)
      # print(can)
  
      if len(grp[0]) > len(grp[1]):
          grp[0], grp[1] = grp[1], grp[0]
      if len(can[1]) > len(can[2]):
          can[1], can[2] = can[2], can[1]
  
      ans = [0] * n
  
      if len(grp[0]) <= len(can[0]):
          for i, v in enumerate(grp[0]):
              ans[v] = can[0].pop()
          can = can[0] + can[1] + can[2]
          for i, v in enumerate(grp[1]):
              ans[v] = can.pop()
          return ans
  
      for i, v in enumerate(grp[0]):
          if can[1]:
              ans[v] = can[1].pop()
          else:
              ans[v] = can[0].pop()
      for i, v in enumerate(grp[1]):
          if can[2]:
              ans[v] = can[2].pop()
          else:
              ans[v] = can[0].pop()
      return ans
  
  
  n = int(input())
  links = [set() for _ in range(n)]
  for line in sys.stdin:
      a, b = map(int, line.split())
      a -= 1
      b -= 1
      links[a].add(b)
      links[b].add(a)
  print(*solve(n, links))
  
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."}]