Problem:


Score : 600 points

Problem 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.

Constraints

2\leq N\leq 2\times 10^5

1\leq a_i, b_i \leq N

The given graph is a tree.

Input

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}

Output

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.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

1 2 5 4 3 

The distance between two vertices is 3 for the two pairs (2, 4) and (2, 5).

p_2 + p_4 = 6

p_2\times p_5 = 6

Thus, this permutation satisfies the condition.



Sample input:
5
1 2
1 3
3 4
3 5


Sample output:
1 2 5 4 3

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import collections


N = int(input())
tree = {i: set() for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)

distance = collections.defaultdict(lambda: collections.defaultdict(list))
visited = set()
for i in range(1, N + 1):
    if i in visited:
        continue
    queue = collections.deque([(0, i)])
    visited.add(i)
    while queue:
        d, cur = queue.popleft()
        for j in tree[cur]:
            if j not in visited:
                distance[i][d + 1].append(j)
                queue.append((d + 1, j))
                visited.add(j)
indices = []
for i, d in distance.items():
    if 3 in d:
        indices.extend([(i, j) for j in d[3]])
    if 1 in d and 2 in d:
        for j in d[1]:
            for k in d[2]:
                if k not in tree[j]:
                    indices.append((j, k))
del distance
del tree
del visited

count = collections.Counter([i for x in indices for i in x])
indices2 = collections.defaultdict(list)
for i, j in indices:
    if count[i] > count[j]:
        indices2[i].append(j)
    else:
        indices2[j].append(i)

del count
del indices


pool = set(range(1, N + 1))
three = set()
for x in pool:
    if x % 3 == 0:
        three.add(x)
pool -= three
rest = {i: set() for i in range(1, 3)}
for x in pool:
    rest[x % 3].add(x)

perm = [0] * N
for i, js in indices2.items():
    if three and pool:
        perm[i - 1] = three.pop()
        for j in js:
            if rest[1]:
                perm[j - 1] = rest[1].pop()
            elif rest[2]:
                perm[j - 1] = rest[2].pop()
            elif three:
                perm[j - 1] = three.pop()
            else:
                print(-1)
                break

    elif rest[1] and rest[2]:
        if len(rest[1]) > len(rest[2]):
            perm[i - 1] = rest[2].pop()
            for j in js:
                if rest[1]:
                    perm[j - 1] = rest[1].pop()
                elif three:
                    perm[j - 1] = three.pop()
                else:
                    print(-1)
                    break
        else:
            perm[i - 1] = rest[1].pop()
            for j in js:
                if rest[2]:
                    perm[j - 1] = rest[2].pop()
                elif three:
                    perm[j - 1] = three.pop()
                else:
                    print(-1)
                    break
    else:
        print(-1)
        break
else:
    rest = rest[1] | rest[2]
    if rest:
        for i in range(N):
            if perm[i] == 0:
                perm[i] = rest.pop()
    print(*perm)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from itertools import permutations
def main():
    N = int( input())
    E = [[] for _ in range(N)]
    AB = [ tuple( map( lambda x:int(x)-1, input().split())) for _ in range(N-1)]
    T = [0]*N
    for a, b in AB:
        E[a].append(b)
        E[b].append(a)
        T[a] += 1
        T[b] += 1
    d = deque()
    P = [-1]*N
    F = [[] for _ in range(6)]
    for i in range(N):
        if T[i] == 1:
            P[i] = 0
            F[0].append(i)
            d.append(i)
            break

    while d:
        v = d.popleft()
        n = P[v]
        for w in E[v]:
            if P[w] == -1:
                d.append(w)
                P[w] = (n+1)%6
                F[(n+1)%6].append(w)



    # oned = deque([ i*3+1 for i in range(one+1)])
    # twod = deque([ i*3+2 for i in range(two+1)])
    L = [ len(F[i]) for i in range(6)]
    check = True
    for q in permutations( range(3)):
        for i in range(8):
            p = [i%2, i//2%2, i//4%2]
            check = True
            count = [N//3, (N+2)//3, (N+1)//3]
            for l in range(3):
                j = q[l]
                if p[j] == 0:
                    s = 1
                    t = 2
                else:
                    s = 2
                    t = 1
            
                if count[s] > L[j]:
                    count[s] -= L[j]
                else:
                    c = L[j] - count[s]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c

                if count[t] > L[j+3]:
                    count[t] -= L[j+3]
                else:
                    c = L[j+3] - count[t]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c
            if check:
                break
        if check:
            break

    count = [N//3, (N+2)//3, (N+1)//3]
    ds = [deque([ i*3+3 for i in range(count[0])]),  deque([ i*3+1 for i in range(count[1])]),  deque([ i*3+2 for i in range(count[2])])]
    ANS = [0]*N
    for j in range(3):
        i = q[j]
        x = i
        y = i+3
        if p[i] == 0:
            s = 1
            t = 2
        else:
            s = 2
            t = 1
        for w in F[x]:
            if ds[s]:
                count[s] -= 1
                ANS[w] = ds[s].popleft()
            elif ds[0]:
                count[0] -= 1
                ANS[w] = ds[0].popleft()
            else:
                count[t] -= 1
                ANS[w] = ds[t].popleft()

        for w in F[y]:
            if ds[t]:
                count[t] -= 1
                ANS[w] = ds[t].popleft()
            elif:
                count[0] -= 1
                ANS[w] = ds[0].popleft()
            else:
                count[s] -= 1
                ANS[w] = ds[s].popleft()

               
    print( " ".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
if N == 3:
    print(1, 2, 3)


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        for node in self.linked:
            if node == parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

# usokaihou
root = nodes[1]
root.set_rank(None, 0)

group = [[], [], []]
for node in nodes.values():
    group[node.rank % 3].append(node)
group.sort(key=len)
result = {}
x1 = set()
x2 = set()
x3 = set()

for i in range(1, N + 1):
    if i % 3 == 1:
        x1.add(i)
    elif i % 3 == 2:
        x2.add(i)
    else:
        x3.add(i)

for node in group[0]:
    result[node.v] = x3.pop()

for node in group[1]:
    if x2:
        result[node.v] = x2.pop()
    else:
        result[node.v] = x3.pop()

for node in group[2]:
    if x1:
        result[node.v] = x1.pop()
    elif x2:
        result[node.v] = x2.pop()
    else:
        result[node.v] = x3.pop()

print(' '.join(str(result[i]) for i in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from itertools import permutations
def main():
    N = int( input())
    E = [[] for _ in range(N)]
    AB = [ tuple( map( lambda x:int(x)-1, input().split())) for _ in range(N-1)]
    T = [0]*N
    for a, b in AB:
        E[a].append(b)
        E[b].append(a)
        T[a] += 1
        T[b] += 1
    d = deque()
    P = [-1]*N
    F = [[] for _ in range(6)]
    for i in range(N):
        if T[i] == 1:
            P[i] = 0
            F[0].append(i)
            d.append(i)
            break

    while d:
        v = d.popleft()
        n = P[v]
        for w in E[v]:
            if P[w] == -1:
                d.append(w)
                P[w] = (n+1)%6
                F[(n+1)%6].append(w)



    # oned = deque([ i*3+1 for i in range(one+1)])
    # twod = deque([ i*3+2 for i in range(two+1)])
    L = [ len(F[i]) for i in range(6)]
    check = True
    for q in permutations( range(3)):
        for i in range(8):
            p = [i%2, i//2%2, i//4%2]
            check = True
            count = [N//3, (N+2)//3, (N+1)//3]
            for l in range(3):
                j = q[l]
                if p[j] == 0:
                    s = 1
                    t = 2
                else:
                    s = 2
                    t = 1
            
                if count[s] > L[j]:
                    count[s] -= L[j]
                else:
                    c = L[j] - count[s]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c

                if count[t] > L[j+3]:
                    count[t] -= L[j+3]
                else:
                    c = L[j+3] - count[t]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c
            if check:
                break
        if check:
            break

    count = [N//3, (N+2)//3, (N+1)//3]
    ds = [deque([ i*3+3 for i in range(count[0])]),  deque([ i*3+1 for i in range(count[1])]),  deque([ i*3+2 for i in range(count[2])])]
    ANS = [0]*N
    for j in range(3):
        i = q[j]
        x = i
        y = i+3
        if p[i] == 0:
            s = 1
            t = 2
        else:
            s = 2
            t = 1
        for w in F[x]:
            if ds[s]:
                count[s] -= 1
                ANS[w] = ds[s].popleft()
            else:
                count[0] -= 1
                ANS[w] = ds[0].popleft() 

        for w in F[y]:
            if ds[t]:
                count[t] -= 1
                ANS[w] = ds[t].popleft()
            else:
                count[0] -= 1
                ANS[w] = ds[0].popleft() 
               
    print( " ".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

mem = [[[] for _ in range(2)] for _ in range(2)]
for i,d in enumerate(depth):
    if d==0: continue
    if d%2:
        mem[0][0].append(i)
        mem[1][1].append(i)
    else:
        mem[0][1].append(i)
        mem[1][0].append(i)

for k in range(2):
    ans = [None] * N
    for i in range(1,N+1):
        if i==3:
            ans[0] = 3
            continue
        if i%3==0:
            if len(mem[k][0])==0 and len(mem[k][1])==0:
                break
            if len(mem[k][0]) <= len(mem[k][1]):
                j = mem[k][1].pop()
            else:
                j = mem[k][0].pop()
        elif i%3==1:
            if len(mem[k][0])==0:
                break
            j = mem[k][0].pop()
        else:
            if len(mem[k][1])==0:
                break
            j = mem[k][1].pop()
        ans[j] = i
    else:
        print(*ans)
        exit()
assert False

Submission status: Runtime Error

Solution code:
import itertools

N = int(input())
edges = [list(map(int,input().split())) for _ in range(N-1)]

A  = [[] for j in range(N+1)]
for edge in edges:
  A[edge[0]].append([edge[1]])
  A[edge[1]].append([edge[0]])


def dfs(A, s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + 1
            dfs(A, v[0])

pair = []
for i in range(1,N+1):
    depth = [-1] * (N + 1)
    depth[i] = 0
    dfs(A, i)
    for j,d in enumerate(depth):
        if d ==3:
            pair.append([i,j])

cand = list(itertools.permutations(list(range(1,N+1))))
flg = 1
for a in cand:
    for i in range(len(pair)):
        i1,i2= pair[i][0]-1,pair[i][1]-1
        if (a[i1]+a[i2])%3!=0 and (a[i1]*a[i2])%3!=0:
            break
        elif i == len(pair)-1:
            print(a)
            flg = 0
            break
    if flg ==0:
        break
if flg ==1:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

from collections import deque

def calc_dist(G, start):
    que = deque()
    dep = [-1]*n
    que.append((-1,start,0))
    while que:
        p,v,d = que.pop()
        dep[v]=d
        for to in G[v]:
            if to != p:
                que.append((v,to,d+1))
    return dep

dep0 = calc_dist(G,0)
m = max(dep0)
left = dep0.index(m)
dep1 = calc_dist(G,left)
m = max(dep1)
right = dep1.index(m)
dep2 = calc_dist(G, right)

x = sum(i%2==0 for i in dep1)
y = n - x
ok = set()
for i in range(n):
    ma = max(dep1[i], dep2[i])
    if ma < 3:
        if dep1[i]%2 == 0:
            x -= 1
        else:
            y -= 1
        ok.add(i)

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)

ans = [0]*n
if x<y:
    one, two = two, one
for i in range(n):
    if i in ok:
        continue
    if dep1[i]%2 == 0:
        if one:
            ans[i] = one.pop()
        else:
            ans[i] = three.pop()
    else:
        if two:
            ans[i] = two.pop()
        else:
            ans[i] = three.pop()
res = one+two+three
for i in ok:
    ans[i] = res.pop()

print(*ans)

Submission status: Runtime Error

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    N=2**N-1
    M=2**M-1
    ans = [[1 if j&1 else (i&1)^1 for i in range(M)] for j in range(N)]
    for a in ans:
        print(*a,sep="")
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
import itertools

N = int(input())
#g = [[0]*N]*Nバグ
g = [[0]*N for _ in range(N)]

def all_pairs_shortest_paths(W):
    n = len(W)
    res = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = math.inf
            res[i][j] = res[j][i] = val
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

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

r = all_pairs_shortest_paths(g)

p = []
for i in range(N):
    for j in range(i, N):
        if r[i][j] == 3:
            p.append((i+1, j+1))

l = [i for i in itertools.permutations(list(range(1, N+1)))]

def check(x, y):
    #和か積が3の倍数か確認
    wa = x + y
    seki = x*y
    if wa%3==0 or seki%3 == 0:
        return True
    return False

def check2(k, p):
    #ある順列について全ペアTrueであるかチェック
    for pair in p:
        i = pair[0]-1
        j = pair[1]-1
        if not check(k[i], k[j]):
            return False
    return True

found = 0
ans = 0
for k in l:
    if check2(k, p):
        found = 1
        break

if found:
    print(" ".join(list(map(str, k))))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from itertools import permutations
def main():
    N = int( input())
    E = [[] for _ in range(N)]
    AB = [ tuple( map( lambda x:int(x)-1, input().split())) for _ in range(N-1)]
    T = [0]*N
    for a, b in AB:
        E[a].append(b)
        E[b].append(a)
        T[a] += 1
        T[b] += 1
    d = deque()
    P = [-1]*N
    F = [[] for _ in range(6)]
    for i in range(N):
        if T[i] == 1:
            P[i] = 0
            F[0].append(i)
            d.append(i)
            break

    while d:
        v = d.popleft()
        n = P[v]
        for w in E[v]:
            if P[w] == -1:
                d.append(w)
                P[w] = (n+1)%6
                F[(n+1)%6].append(w)



    # oned = deque([ i*3+1 for i in range(one+1)])
    # twod = deque([ i*3+2 for i in range(two+1)])
    L = [ len(F[i]) for i in range(6)]
    check = True
    for q in permutations( range(3)):
        for i in range(8):
            p = [i%2, i//2%2, i//4%2]
            check = True
            count = [N//3, (N+2)//3, (N+1)//3]
            for l in range(3):
                j = q[l]
                if p[j] == 0:
                    s = 1
                    t = 2
                else:
                    s = 2
                    t = 1
            
                if count[s] > L[j]:
                    count[s] -= L[j]
                else:
                    c = L[j] - count[s]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c

                if count[t] > L[j+3]:
                    count[t] -= L[j+3]
                else:
                    c = L[j+3] - count[t]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c
            if check:
                break
        if check:
            break

    count = [N//3, (N+2)//3, (N+1)//3]
    ds = [deque([ i*3+3 for i in range(count[0])]),  deque([ i*3+1 for i in range(count[1])]),  deque([ i*3+2 for i in range(count[2])])]
    ANS = [0]*N
    for j in range(3):
        i = q[j]
        x = i
        y = i+3
        if p[i] == 1:
            x, y = y, x
        # if L[x] > L[y]:
        #     x, y = y, x
        if count[0] < count[1]:
            s = 1
            t = 2
        else:
            s = 2
            t = 1
        for w in F[x]:
            if ds[s]:
                count[s] -= 1
                ANS[w] = ds[s].popleft()
            else:
                count[0] -= 1
                ANS[w] = ds[0].popleft() 

        for w in F[y]:
            if ds[t]:
                count[t] -= 1
                ANS[w] = ds[t].popleft()
            else:
                count[0] -= 1
                ANS[w] = ds[0].popleft() 
               
    print( " ".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
from heapq import heappush, heappop


def dfs(s, v, step):
    if step == 3:
        edge3[s].add(v)
        edge3[v].add(s)
    else:
        for nv in edge[v]:
            if status[nv] == 0:
                status[nv] = 1
                dfs(s, nv, step + 1)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
edge3 = [set() for _ in range(N)]
for s in range(N):
    status = [0] * N
    status[s] = 1
    dfs(s, s, 0)

# print(edge3)
q = []
for i, e3 in enumerate(edge3):
    heappush(q, (-len(e3), i))

x = (y for y in range(N + 1) if y % 3 != 0)
z = 1
Z = N // 3
ans = [None] * N
for i in range(N):
    lenE3, v = heappop(q)
    if ans[v] is None:
        if z <= Z:
            ans[v] = 3 * z
            z += 1
        else:
            ans[v] = next(x)
        for e3 in edge3[v]:
            if ans[e3] is None:
                ans[e3] = next(x)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
ab = [read_int() for _ in range(N - 1)]

adj_list = defaultdict(list)
# adj_list: key...int start, value... [] ends
for e in ab:
    adj_list[e[0]].append(e[1])
    adj_list[e[1]].append(e[0])
# print(adj_list)

res = []
def solve():
    ans = [i for i in range(1, N + 1)]
    for e in range(1, N + 1):
        # if e != 2:
        #     continue
        rec(e, 0, [])
    for r in res:
        a1 = ans[r[0] - 1]
        a2 = ans[r[1] - 1]
        if (a1 + a2) % 3 != 0 and (a1 * a2) % 3 != 0:
            swapped = False
            for i in range(2, N, 3):
                if ans[i] == i + 1:
                    ans[i], ans[r[1] - 1] = ans[r[1] - 1], ans[i]
                    swapped = True
                if swapped: break
            if not swapped: return -1
    return ans

def rec(e, i, vis):
    vis.append(e)
    if i == 3 and vis[0] < e:
        # for adj in adj_list[e]:
            # res.append([vis[0], adj])
            # print([vis[0], adj], vis)
        res.append([vis[0], e])

        return
    if len(adj_list[e]) == 0: return
    for adj in adj_list[e]:
        if not (adj in vis):
            # print(adj, i, vis)
            rec(adj, i + 1, vis)


if __name__ == "__main__":
    ans = solve()
    print(' '.join(map(str,ans)))
    # print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]

# print(ab)

tree = [[] for _ in range(N+1)]
for a, b in ab:
    tree[a].append(b)
    tree[b].append(a)

from collections import deque

q = deque([1])
dist = [float('inf')]*(N+1)
dist[1] = 0
seen = {1}

while q:
    x = q.popleft()
    children = tree[x]
    for i in children:
        dist[i] = min(dist[i], dist[x]+1)
        if i not in seen:
            q.append(i)
            seen.add(i)

distm = {i:[] for i in range(N+1)}

for i, d in enumerate(dist):
    if i == 0:
        continue
    distm[d].append(i)

k = []

from itertools import product

for i in range(N+1):
    if i > 2:
        k.extend(product(distm[i-3], distm[i]))
    if i == 1:
        ones = distm[1]
        for o in ones:
            twos = set(distm[2]) - set(tree[o])
            for t in twos:
                k.append((o, t))

# print(k)

ans = [0]*N
threes = set()
nos = set()
i = 1
for a, b in k:
    if a not in threes:
        try:
            ans[3*i-1] = a
            threes.add(a)
        except:
            nos.add(a)
            pass
    nos.add(b)
    i += 1

lnos = list(nos)
i = 1
for j in range(len(lnos)):
    if j % 2 == 0:
        ans[3*i-2] = lnos[j]
    else:
        ans[3*i] = lnos[j]

nokori = set(range(1, N+1)) - threes - nos
# print('nokori', nokori)
nokori = list(nokori)
# print('nokori', nokori)


for i in range(N):
    if ans[i] == 0:
        # print(nokori)
        # print(nokori.pop())
        ans[i] = nokori.pop()
    # print(ans)
print(ans)