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 = int(input())
  
  a = [None] * N
  b = [None] * N
  
  ps = {}
  cs = {}
  for i in range(N - 1):
      a[i], b[i] = [int(n) for n in input().split()]
      if a[i] < b[i]:
          ps[b[i]] = a[i]
          if a[i] not in cs:
              cs[a[i]] = []
          cs[a[i]].append(b[i])
      else:
          ps[a[i]] = b[i]
          if b[i] not in cs:
              cs[b[i]] = []
          cs[b[i]].append(a[i])
  
  dd = {}
  
  
  def d(i, j):
      if i < j:
          p = i
          c = j
      elif i == j:
          return 0
      else:
          p = j
          c = i
      if (p, c) in dd:
          return dd[(p, c)]
      dd[(p, c)] = 1 + d(ps[c], p)
      return dd[(p, c)]
  
  
  p = list(range(1, N + 1))
  
  for i in range(N - 1):
      for j in range(i + 1, N):
          if d(i + 1, j + 1) == 3:
              if (p[i] + p[j]) % 3 != 0 and (p[i] * p[j]) % 3 != 0:
                  e = p[i]
                  p[i] = p[i + 1]
                  p[i + 1] = e
  
  p = map(lambda a: str(a), p)
  print(" ".join(p))
  
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."}]