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: def dijkstra(s, n, w, cost):
      # 始点sから各頂点への最短距離
      # n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
      d = [float("inf")] * n
      used = [False] * n
      d[s] = 0
  
      while True:
          v = -1
          # まだ使われてない頂点の中から最小の距離のものを探す
          for i in range(n):
              if (not used[i]) and (v == -1):
                  v = i
              elif (not used[i]) and d[i] < d[v]:
                  v = i
          if v == -1:
              break
          used[v] = True
  
          for j in range(n):
              d[j] = min(d[j], d[v] + cost[v][j])
      return d
  
  
  ################################
  # n, w = map(int, input().split())  # n:頂点数　w:辺の数
  n = int(input())  # n:頂点数　w:辺の数
  w = n - 1
  
  cost = [[float("inf") for i in range(n)] for i in range(n)]
  # cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
  z = 1
  for i in range(w):
      # x, y, z = map(int, input().split())
      x, y = map(int, input().split())
      cost[x - 1][y - 1] = z
      cost[y - 1][x - 1] = z
  # print(dijkstra(1, n, w, cost))
  li1 = []
  for i in range(n):
      for j in range(n):
          k = dijkstra(i, n, w, cost)
          if k[j] == 3:
              li1.append([i, j])
  ans = [1] * n
  for i in li1:
      ans[i[0]] = 3
      ans[i[1]] = 3
  
  if li1 == []:
      print("-1")
  else:
      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."}]