Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

group = [[0], []]
idx = 1
stack = [0]
while stack:
  tmp = stack
  stack = []
  while tmp:
    v = tmp.pop()
    for u in edge[v]:
      if u not in group[idx]:
        group[idx].append(u)
        stack.append(u)
  idx ^= 1

p = [0] * n
group.sort(key=len)
if len(group[0]) <= n // 3:
  three = 3
  while group[0]:
    v = group[0].pop()
    p[v] = three
    three += 3
  while three <= n:
    v = group[1].pop()
    p[v] = three
    three += 3
  i = 0
  while group[1]:
    v = group[1].pop()
    p[v] = 3 * i + 1
    if group[1]:
      v = group[1].pop()
      p[v] = 3 * i + 2
      i += 1
else:
  three = 3
  for two in range(2, n+1, 3):
    v = group[0].pop()
    p[v] = two
  while group[0]:
    v = group[0].pop()
    p[v] = three
    three += 3
  for one in range(1, n+1, 3):
    v = group[1].pop()
    p[v] = one
  while group[1]:
    v = group[1].pop()
    p[v] = three
    three += 3
print(' '.join(map(str, p)))

Fixed submission:
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)

three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))

Buggy python submission (verdict: Runtime Error):
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
group = [[0], []]
idx = 1
stack = [0]
tmp = True
while tmp:
  tmp = []
  while stack:
    v = stack.pop()
    for u in edge[v]:
      if u not in group[idx ^ 1]:
        group[idx].append(u)
        tmp.append(u)
  idx ^= 1
one = n // 3 + int(n % 3 > 0)
two = n // 3 + int(n % 3 == 2)
three = n // 3
p = [0] * n
group.sort(key=len)
if len(group[0]) >= two:
  index3 = 1
  for i in range(two):
    v = group[0].pop()
    p[v] = 3 * i + 2
  while group[0]:
    v = group[0].pop()
    p[v] = 3 * index3
    index3 += 1
  for i in range(one):
    v = group[1].pop()
    p[v] = 3 * i + 1
  while group[1]:
    v = group[1].pop()
    p[v] = 3 * index3
    index3 += 1
else:
  print(-1)

Fixed submission:
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)

three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))