Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(cl)
if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      else: res[i] = nm[2].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      else: res[i] = nm[2].pop()
  print(*res[1: ])
  exit(0)
#print(nm)
#print(cl, nm)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        f = 1
        break
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        f = 1
        break
if f:
  nm = [[] for _ in range(3)]
  for i in range(1, N + 1): nm[i % 3].append(i)
  res = [0] * (N + 1)
  for i in range(1, N + 1):
    if cl[i] == 0:
      if len(nm[1]):
        res[i] = nm[1].pop()
      else:
        if len(nm[0]):
          res[i] = nm[0].pop()
        else:
          print(-1)
          exit(0)
    else:
      if len(nm[2]):
        res[i] = nm[2].pop()
      else:
        if len(nm[0]):
          res[i] = nm[0].pop()
        else:
          print(-1)
          exit(0)
print(*res[1: ])

Fixed submission:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2
    dfs(y)

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(cl)
if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
#print(nm)
#print(cl, nm)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2

dfs(1)
bl = cl.count(1)
wh = N - bl

nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(nm)

res = [0] * (N + 1)
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Fixed submission:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2
    dfs(y)

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(cl)
if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
#print(nm)
#print(cl, nm)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2

dfs(1)
bl = cl.count(1)
wh = N - bl

nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(nm)

res = [0] * (N + 1)
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Fixed submission:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2
    dfs(y)

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(cl)
if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
#print(nm)
#print(cl, nm)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

table = [[] for _ in range(N + 1)]
sta = []
for x in range(1, N + 1):
  Q = dq([])
  Q.append((x, 0))
  vis = set()
  while len(Q):
    y, n = Q.popleft()
    if n == 3:
      table[x].append(y)
      continue
    for q in e[y]:
      if q in vis: continue
      vis.add(q)
      Q.append((q, n + 1))
  sta.append((len(table[x]), x))
sta.sort()
nm = [0] * 3
for x in range(1, N + 1): nm[x % 3] += 1

res = [0] * (N + 1)

while nm[0]:
  _, x = sta.pop()
  res[x] = nm[0] * 3
  nm[0] -= 1

while nm[1]:
  _, x = sta[-1]
  ng = 0
  for y in table[x]:
    if res[y] % 3 == 1:
      ng = 1
      break
  if ng:
    continue
  sta.pop()
  res[x] = (nm[1] - 1) * 3 + 1
  nm[1] -= 1

while nm[2]:
  _, x = sta[-1]
  ng = 0
  for y in table[x]:
    if res[y] % 3 == 2:
      ng = 1
      break
  if ng: continue
  sta.pop()
  res[x] = (nm[2] - 1) * 3 + 2
  nm[2] -= 1

print(*res[1: ])

Fixed submission:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2
    dfs(y)

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(cl)
if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
#print(nm)
#print(cl, nm)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

table = [[] for _ in range(N + 1)]
sta = []
for x in range(1, N + 1):
  Q = dq([])
  Q.append((x, 0))
  vis = set()
  while len(Q):
    y, n = Q.popleft()
    if n == 3:
      table[x].append(y)
      continue
    for q in e[y]:
      if q in vis: continue
      vis.add(q)
      Q.append((q, n + 1))
  sta.append((len(table[x]), x))
sta.sort()
nm = [0] * 3
for x in range(1, N + 1): nm[x % 3] += 1

res = [0] * (N + 1)

while nm[0]:
  _, x = sta.pop()
  res[x] = nm[0] * 3
  nm[0] -= 1

while nm[1]:
  _, x = sta.pop()
  ng = 0
  for y in table[x]:
    if res[y] % 3 == 1:
      ng = 1
      break
  if ng: continue
  res[x] = (nm[1] - 1) * 3 + 1
  nm[1] -= 1

while nm[2]:
  _, x = sta.pop()
  ng = 0
  for y in table[x]:
    if res[y] % 3 == 2:
      ng = 1
      break
  if ng: continue
  res[x] = (nm[2] - 1) * 3 + 2
  nm[2] -= 1

print(*res[1: ])

Fixed submission:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2
    dfs(y)

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(cl)
if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
#print(nm)
#print(cl, nm)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])