Problem p02749 (python)

Fixed submission:
from collections import deque

N = int(input())
tree = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

d = deque([[0, -1]])
dist = [0] * N
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dist[child] = (dist[node] + 1) % 2
    d.appendleft([child, node])

count0 = dist.count(0)
count1 = N - count0
s = [set(), set(), set()]
for i in range(1, N+1):
  s[i%3].add(i)
if count0 > N//3:
  if count1 > N//3:
    for i in range(N):
      if dist[i]:
        if s[2]:
          dist[i] = s[2].pop()
        else:
          dist[i] = s[0].pop()
      else:
        if s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
  else:
    for i in range(N):
      if dist[i]:
        dist[i] = s[0].pop()
      else:
        if s[2]:
          dist[i] = s[2].pop()
        elif s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
else:
  for i in range(N):
    if dist[i]:
      if s[2]:
        dist[i] = s[2].pop()
      elif s[1]:
        dist[i] = s[1].pop()
      else:
        dist[i] = s[0].pop()
    else:
      dist[i] = s[0].pop()

print(*dist)

Buggy submission (verdict: Runtime Error):
from collections import deque

N = int(input())
tree = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

d = deque([[0, -1]])
dist = [0] * N
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dist[child] = (dist[node] + 1) % 2
    d.appendleft([child, node])

count0 = dist.count(0)
count1 = N - count0
s = [set(), set(), set()]
for i in range(1, N+1):
  s[i%3].add(i)
if count0 >= N//3:
  if count1 >= N//3:
    for i in range(N):
      if dist[i]:
        if s[2]:
          dist[i] = s[2].pop()
        else:
          dist[i] = s[0].pop()
      else:
        if s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
  else:
    for i in range(N):
      if dist[i]:
        dist[i] = s[0].pop()
      else:
        if s[2]:
          dist[i] = s[2].pop()
        elif s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
else:
  for i in range(N):
    if dist[i]:
      if s[2]:
        dist[i] = s[2].pop()
      elif s[1]:
        dist[i] = s[1].pop()
      else:
        dist[i] = s[0].pop()
    else:
      dist[i] = s[0].pop()

print(*dist)

Buggy submission (verdict: Runtime Error):
from collections import deque

N = int(input())
if N == 2:
  print(1, 2)
  quit()
elif N == 3:
  print(1, 2, 3)
  quit()

tree = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

d = deque([[0, -1]])
g = dict(zip(range(N), [[] for i in range(N)]))
p = dict(zip(range(N), [[] for i in range(N)]))
c = dict(zip(range(N), [[] for i in range(N)]))
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    d.appendleft([child, node])
    if par >= 0:
      g[par].append(child)
    p[node].append(child)
    c[child].append(node)

s = dict(zip(range(N), [[] for i in range(N)]))
for gran in g:
  _g = g[gran]
  _p = p[gran]
  _c = c[gran]
  if _g:
    if _p:
      for __g in _g:
        for __p in _p:
          if __p in tree[__g]:
            continue
          if __g < __p:
            s[__g].append(__p)
          else:
            s[__p].append(__g)
    if _c:
      for __g in _g:
        for __c in _c:
          if __g < __c:
            s[__g].append(__c)
          else:
            s[__c].append(__g)

m0 = N//3
m2 = (N - m0)//2
m1 = N - m0 - m2
if m1*m2 + m0*(m1+m2) + m0*(m0-1)//2 < len(s):
  print(-1)
else:
  _m0 = 1
  num = [0] * N
  nums1 = set([i for i in range(1, N+1)][::3])
  nums2 = set([i for i in range(2, N+1)][::3])
  for n in s:
    if _m0 <= m0:
      num[n] = 3*_m0
      _m0 += 1
    else:
      pairs = s[n]
      if num[n] == 0:
        num[n] = 1
      if num[n] == 1:
        for pa in pairs:
          num[pa] = 2
      else:
        for pa in pairs:
          num[pa] = 1
  for i in range(N):
    if num[i] == 1:
      num[i] = nums1.pop()
    elif num[i] == 2:
      num[i] = nums2.pop()      
  print(*num)