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: from sys import exit
  import sys
  
  sys.setrecursionlimit(1000000000)
  
  N = int(input())
  
  
  class Node:
      def __init__(self, index):
          self.index = index
          self.paths = []
          self.num = -1
  
  
  nodes = [Node(i) for i in range(N)]
  one = [i for i in range(1, N + 1, 3)]
  two = [i for i in range(2, N + 1, 3)]
  three = [i for i in range(3, N + 1, 3)]
  
  for _ in range(N - 1):
      a, b = map(int, input().split())
      nodes[a - 1].paths.append(b - 1)
      nodes[b - 1].paths.append(a - 1)
  
  
  def rec(node, key, passed):
      passed.add(node.index)
      if key == 1:
          if len(one) > 0:
              node.num = one.pop()
          elif len(three) > 0:
              node.num = three.pop()
          else:
              print(-1)
              exit()
      else:  # key == -1
          if len(two) > 0:
              node.num = two.pop()
          elif len(three) > 0:
              node.num = three.pop()
          else:
              print(-1)
              exit()
      for path in node.paths:
          if path in passed:
              continue
          passed = rec(nodes[path], key * (-1), passed)
      return passed
  
  
  _ = rec(nodes[0], 1, set())
  
  ans = [node.num for node in nodes]
  print(*ans)
  
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."}]