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: #!/usr/bin/python3
  # -*- coding: utf-8 -*-
  node_dict = {}
  ans_dict = {}
  ans_count = {}
  
  
  def check(i, old_no, deep, start):
      deep += 1
      if deep == 3:
          if i in ans_dict:
              ans_dict[i].append(start)
              ans_count[i] += 1
          else:
              ans_dict[i] = [start]
              ans_count[i] = 1
          if start in ans_dict:
              ans_dict[start].append(i)
              ans_count[start] += 1
          else:
              ans_dict[start] = [i]
              ans_count[start] = 1
          return 0
      for key in node_dict[i]:
          if key == old_no:
              continue
          check(key, i, deep, start)
      return 0
  
  
  n = int(input())
  ans_list = [0] * n
  for i in range(1, n):
      a, b = map(int, input().split())
      if a in node_dict:
          node_dict[a].append(b)
      else:
          node_dict[a] = [b]
      if b in node_dict:
          node_dict[b].append(a)
      else:
          node_dict[b] = [a]
  
  for i in range(1, n):
      for key in node_dict[i]:
          check(key, i, 0, i)
  
  count = 0
  count_12 = 0
  count_3 = 0
  for key, v in sorted(ans_count.items(), key=lambda x: -x[1]):
      if count == n:
          break
      if ans_list[key - 1] == 0:
          if (count_3 + 1) * 3 <= n:
              count += 1
              count_3 += 1
              ans_list[key - 1] = 3 * count_3
              for key1 in ans_dict[key]:
                  if ans_list[key1 - 1] == 0:
                      count_12 += 1
                      if count_12 % 3 == 0:
                          count_12 += 1
                      ans_list[key1 - 1] = count_12
          else:
              count_12 += 1
              if count_12 % 3 == 0:
                  count_12 += 1
              ans_list[key - 1] = count_12
  
  for i in range(0, n):
      if ans_list[i] == 0:
          count_12 += 1
          if count_12 % 3 == 0:
              count_12 += 1
          ans_list[key - 1] = count_12
      print(str(ans_list[i]), end="")
      print(" ", end="")
  
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."}]