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, collections as cl, bisect as bs
  
  sys.setrecursionlimit(100000)
  input = sys.stdin.readline
  mod = 10**9 + 7
  Max = sys.maxsize
  
  
  def l():  # intのlist
      return list(map(int, input().split()))
  
  
  def m():  # 複数文字
      return map(int, input().split())
  
  
  def onem():  # Nとかの取得
      return int(input())
  
  
  def s(x):  # 圧縮
      a = []
      aa = x[0]
      su = 1
      for i in range(len(x) - 1):
          if aa != x[i + 1]:
              a.append([aa, su])
              aa = x[i + 1]
              su = 1
          else:
              su += 1
      a.append([aa, su])
      return a
  
  
  def jo(x):  # listをスペースごとに分ける
      return " ".join(map(str, x))
  
  
  def max2(x):  # 他のときもどうように作成可能
      return max(map(max, x))
  
  
  def In(x, a):  # aがリスト(sorted)
      k = bs.bisect_left(a, x)
      if k != len(a) and a[k] == x:
          return True
      else:
          return False
  
  
  """
  def nibu(x,n,r):
      ll = 0
      rr = r
      while True:
          mid = (ll+rr)//2
  
      if rr == mid:
          return ll
      if (ここに評価入れる):
          rr = mid
      else:
          ll = mid+1
  
  """
  
  import collections
  import itertools
  import operator
  
  
  class UnionFind:
      def __init__(self, x):
          class KeyDict(dict):
              def __missing__(self, key):
                  self[key] = key
                  return key
  
          self.parent = KeyDict()
          self.rank = collections.defaultdict(int)
          self.size = collections.defaultdict(lambda: 1)
          if x is not None:
              for elem in range(x + 1):
                  _, _, _ = self.parent[elem], self.rank[elem], self.size[elem]
  
      def find(self, x):
          if self.parent[x] == x:
              return x
          else:
              self.parent[x] = self.find(self.parent[x])
              return self.parent[x]
  
      def unite(self, x, y):
          x = self.find(x)
          y = self.find(y)
          if not self.are_same(x, y):
              xx = self.size[x]
              yy = self.size[y]
              if self.rank[x] < self.rank[y]:
                  self.parent[x] = y
                  self.size[y] += xx
              else:
                  self.parent[y] = x
                  self.size[x] += yy
          if self.rank[x] == self.rank[y]:
              self.rank[x] += 1
  
      def Size(self, x):
          return self.size[self.find(x)]
  
      def are_same(self, x, y):
          """print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))"""
          return self.find(x) == self.find(y)
  
      def grouper(self):
          roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
          root = operator.itemgetter(1)
          for _, group in itertools.groupby(sorted(roots, key=root), root):
              yield [x for x, _ in group]
  
  
  n = onem()
  
  tr = [[] for i in range(n)]
  po = [[] for i in range(n)]
  
  for i in range(n - 1):
      a, b = m()
      tr[a - 1].append(b - 1)
      tr[b - 1].append(a - 1)
  
  de = cl.deque([[0, -1, -1]])
  
  while de:
      data = de.popleft()
      for i in range(len(tr[data[0]])):
          if tr[data[0]][i] != data[1]:
              de.append([tr[data[0]][i], data[0], data[1]])
              if data[1] != -1:
                  for j in range(len(tr[data[1]])):
                      if tr[data[1]][j] != data[0]:
                          po[tr[data[0]][i]].append(tr[data[1]][j])
                          po[tr[data[1]][j]].append(tr[data[0]][i])
              if data[2] != -1:
                  po[data[2]].append(tr[data[0]][i])
                  po[tr[data[0]][i]].append(data[2])
  
  co = [[len(po[i]), i] for i in range(n)]
  
  co.sort(reverse=True)
  
  p0 = 0
  p1 = 0
  p2 = 0
  
  num = [0 for i in range(n)]
  
  for i in range(n):
      ppp = co[i][1]
      if (p0 + 1) * 3 < n:
          num[ppp] = (p0 + 1) * 3
          p0 += 1
      else:
          break
  co = 1
  for i in range(n):
      if num[i] == 0:
          num[i] = co
          co += 1
          if co % 3 == 0 and (p0 + 1) * 3 == co:
              continue
          elif co % 3 == 0:
              co += 1
  print(jo(num))
  
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."}]