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

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)
x = [x1, x2, x3]

result = {}


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
        if parent == None:
            result[self.v] = x1.pop()
        else:
            if x[(result[self.parent.v] + 1) % 3]:
                result[self.v] = x[(result[self.parent.v] + 1) % 3].pop()
            elif x1:
                x1.pop()
            elif x2:
                x2.pop()
            else:
                x3.pop()
        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)
print(' '.join(str(result[i]) for i in range(1, N + 1)))

exit()

Submission status: Runtime Error

Solution code:
N = int(input())

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

result = [int(x) for x in range(1, N+1)]
for i in range(N-1):

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
B = []
ans = []

for i in range(N-1):
  a, b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

if (A[2] == B[0]):
  ans = [1, 5, 2, 4, 3]
elif (A[2] == B[1]):
  ans = [1, 2, 5, 4, 3]

print(*ans, sep=' ')

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
from collections import deque

def main():
    n=int(input())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    Depth=[-1]*n
    Depth[0]=0
    q=deque()
    q.append(0)
    while q:
        fr=q.popleft()
        for to in Edges[fr]:
            if Depth[to]==-1:
                Depth[to]=Depth[fr]+1
                q.append(to)
    Group=[[] for _ in range(2)]
    for i in range(n):
        Group[Depth[i]%2].append(i)
    #print(Depth,Group)
    l_even,l_odd=len(Group[0]),len(Group[1])
    #print(l_even,l_odd)
    Ans=[0]*n
    Used=[False]*(n+1)
    if l_even<=l_odd:
        if l_even<n//3:
            tmp_3=3
            tmp_others=1
            for i in range(n):
                if Depth[i]%2==0:
                    Ans[i]=tmp_3
                    Used[tmp_3]=True
                    tmp_3+=3
                else:
                    while tmp_others%3==0 or Used[tmp_others]:
                        tmp_others+=1
                    Ans[i]=tmp_others
                    Used[tmp_others]=True
            print(*Ans)
            exit()
    else:
        if l_odd<n//3:
            tmp_3=3
            tmp_others=1
            for i in range(n):
                if Depth[i]%2==1:
                    Ans[i]=tmp_3
                    Used[tmp_3]=True
                    tmp_3+=3
                else:
                    while tmp_others%3==0 or Used[tmp_others]:
                        tmp_others+=1
                    Ans[i]=tmp_others
                    Used[tmp_others]=True
            print(*Ans)
            exit()
    tmp_odd,tmp_even,tmp_others=1,2,3
    for i in range(n):
        #print(Depth[i])
        if Depth[i]%2==1:
            if tmp_odd<=n:
                #print('A')
                Ans[i]=tmp_odd
                tmp_odd+=3
            else:
                #print('B')
                Ans[i]=tmp_others
                tmp_others+=3
        else:
            if tmp_even<=n:
                #print('C')
                Ans[i]=tmp_even
                tmp_even+=3
            else:
                #print('D')
                Ans[i]=tmp_others
                tmp_others+=3
    print(*Ans)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
x=[[] for i in range(n)]
c=[-1]*n
c[0]=1
for i in range(n-1):
    a,b=map(int,input().split())
    x[a-1].append(b-1)
    x[b-1].append(a-1)

def dfs(i,col):
    for k in x[i]:
        if c[k]==-1:
            c[i]=col
            if col==2:
                dfs(k,1)
            else:
                dfs(k,2)

dfs(0,c[0])
d=[]
e=[]
f=[]
x=n//3+(0 if n%3==0 else 1)
for i in range(n):
    if c[i]==1:
        x=n//3+(0 if n%3==0 else 1)
        if len(d)==x:
            f.append(i+1)
        else:
            d.append(i+1)
    else:
        x=n//3+(1 if n%3==2 else 0)
        if len(e)==x:
            f.append(i+1)
        else:
            e.append(i+1)
ans=[-1]*n
g=[d,e,f]
g.sort(key=lambda x:len(x),reverse=True)
d,e,f=g
for i in range(n):
    if i%3==0:
        ans[i]=d[i//3]
    elif i%3==1:
        ans[i]=e[i//3]
    else:
        ans[i]=f[i//3]
print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    from collections import defaultdict, deque
    import copy

    n = int(input())
    nodes = defaultdict(lambda: deque())
    for _ in range(n-1):
        a, b = map(int, input().split())
        nodes[a].append(b)
        nodes[b].append(a)

    for i, j in nodes.items():
        if len(j) == 1:
            leaf = i
            break

    visited = [False]*n

    odd = True

    odd_num = 0

    depth = -1
    next = deque()
    now = deque([leaf])
    while True:
        depth += 1
        odd = not odd
        if odd:
            while now:
                node = now.pop()
                if visited[node-1] == True:
                    continue
                visited[node-1] = True
                odd_num += 1
                neighbor = copy.deepcopy(nodes[node])
                while neighbor:
                    next.append(neighbor.pop())
        else:
            while now:
                node = now.pop()
                if visited[node-1] == True:
                    continue
                visited[node-1] = True
                neighbor = copy.deepcopy(nodes[node])
                while neighbor:
                    next.append(neighbor.pop())
        now = copy.deepcopy(next)
        if not now:
            break
        next = deque()

    baisuu = 3
    baisuu1 = 1
    baisuu2 = 2
    depth -= 1

    odd = True
    next = deque()
    now = deque([leaf])
    visited = [False]*n

    ans = ['']*n

    if depth > 4:
        if odd_num < n/2:
            if round(n/3) > odd_num:
                print(-1)
                exit()
            while True:
                odd = not odd
                if odd:
                    while now:
                        node = now.pop()
                        if visited[node-1] == True:
                            continue
                        visited[node-1] = True
                        if baisuu2 <= n:
                            ans[node-1] = str(baisuu2)
                            baisuu2 += 3
                        else:
                            ans[node-1] = str(baisuu)
                            baisuu += 3
                        neighbor = copy.deepcopy(nodes[node])
                        while neighbor:
                            next.append(neighbor.pop())
                else:
                    while now:
                        node = now.pop()
                        if visited[node-1] == True:
                            continue
                        visited[node-1] = True
                        if baisuu1 <= n:
                            ans[node-1] = str(baisuu1)
                            baisuu1 += 3
                        else:
                            ans[node-1] = str(baisuu)
                            baisuu += 3
                        neighbor = copy.deepcopy(nodes[node])
                        while neighbor:
                            next.append(neighbor.pop())
                now = copy.deepcopy(next)
                if not now:
                    break
                next = deque()
        else:  # 距離偶数の方が少ない時
            if round(n/3) > (n-odd_num):
                print(-1)
                exit()
            while True:
                odd = not odd
                if not odd:   # 偶数の場合あまり2
                    while now:
                        node = now.pop()
                        if visited[node-1] == True:
                            continue
                        visited[node-1] = True
                        if baisuu2 <= n:
                            ans[node-1] = str(baisuu2)
                            baisuu2 += 3
                        else:
                            ans[node-1] = str(baisuu)
                            baisuu += 3
                        neighbor = copy.deepcopy(nodes[node])
                        while neighbor:
                            next.append(neighbor.pop())
                else:
                    while now:
                        node = now.pop()
                        if visited[node-1] == True:
                            continue
                        visited[node-1] = True
                        if baisuu1 <= n:
                            ans[node-1] = str(baisuu1)
                            baisuu1 += 3
                        else:
                            ans[node-1] = str(baisuu)
                            baisuu += 3
                        neighbor = copy.deepcopy(nodes[node])
                        while neighbor:
                            next.append(neighbor.pop())
                now = copy.deepcopy(next)
                if not now:
                    break
                next = deque()
        print(' '.join(ans))
    elif depth < 3:
        print(' '.join(list(range(1, n+1))))
    elif depth == 3:
        if odd_num < n/2:
            if round((n-2)/3) > (odd_num-1):
                print(-1)
                exit()
            else:
                while True:
                    odd = not odd
                    if odd:
                        while now:
                            node = now.pop()
                            if visited[node-1] == True:
                                continue
                            visited[node-1] = True
                            neighbor = copy.deepcopy(nodes[node])
                            if len(neighbor) > 1:
                                odd_special = node
                                # continue
                            elif baisuu2 <= n:
                                ans[node-1] = str(baisuu2)
                                baisuu2 += 3
                            else:
                                ans[node-1] = str(baisuu)
                                baisuu += 3
                            while neighbor:
                                next.append(neighbor.pop())
                    else:
                        while now:
                            node = now.pop()
                            if visited[node-1] == True:
                                continue
                            visited[node-1] = True
                            neighbor = copy.deepcopy(nodes[node])
                            if len(neighbor) > 1:
                                even_special = node
                                # continue
                            elif baisuu1 <= n:
                                ans[node-1] = str(baisuu1)
                                baisuu1 += 3
                            else:
                                ans[node-1] = str(baisuu)
                                baisuu += 3
                            while neighbor:
                                next.append(neighbor.pop())
                    now = copy.deepcopy(next)
                    if not now:
                        break
                    next = deque()
            if baisuu2 <= n:
                ans[even_special-1] = str(baisuu2)
                baisuu2 += 3
                if baisuu2 <= n:
                    ans[odd_special-1] = str(baisuu2)
                else:
                    ans[odd_special-1] = str(baisuu)
            else:
                ans[even_special-1] = str(baisuu)
                ans[odd_special-1] = str(baisuu+3)
            print(' '.join(ans))
        else:
            if round((n-2)/3) > (n-1-odd_num):
                print(-1)
                exit()
            else:
                while True:
                    odd = not odd
                    if not odd:
                        while now:
                            node = now.pop()
                            if visited[node-1] == True:
                                continue
                            visited[node-1] = True
                            neighbor = copy.deepcopy(nodes[node])
                            if len(neighbor) > 1:
                                odd_special = node
                                # continue
                            elif baisuu2 <= n:
                                ans[node-1] = str(baisuu2)
                                baisuu2 += 3
                            else:
                                ans[node-1] = str(baisuu)
                                baisuu += 3
                            while neighbor:
                                next.append(neighbor.pop())
                    else:
                        while now:
                            node = now.pop()
                            if visited[node-1] == True:
                                continue
                            visited[node-1] = True
                            neighbor = copy.deepcopy(nodes[node])
                            if len(neighbor) > 1:
                                even_special = node
                            elif baisuu1 <= n:
                                ans[node-1] = str(baisuu1)
                                baisuu1 += 3
                            else:
                                ans[node-1] = str(baisuu)
                                baisuu += 3
                            while neighbor:
                                next.append(neighbor.pop())
                    now = copy.deepcopy(next)

                    if not now:
                        break
                    next = deque()
            if baisuu2 <= n:
                ans[even_special-1] = str(baisuu2)
                baisuu2 += 3
                if baisuu2 <= n:
                    ans[odd_special-1] = str(baisuu2)
                else:
                    ans[odd_special-1] = str(baisuu)
            else:
                ans[even_special-1] = str(baisuu)
                ans[odd_special-1] = str(baisuu+3)
            print(' '.join(ans))
    else:
        depth = -1
        if odd_num < n/2:
            if round((n-1)/3) > odd_num:
                print(-1)
                exit()
            else:
                while True:
                    odd = not odd
                    depth += 1
                    if odd:
                        while now:
                            node = now.pop()
                            if visited[node-1] == True:
                                continue
                            visited[node-1] = True
                            neighbor = copy.deepcopy(nodes[node])
                            if baisuu2 <= n:
                                ans[node-1] = str(baisuu2)
                                baisuu2 += 3
                            else:
                                ans[node-1] = str(baisuu)
                                baisuu += 3
                            while neighbor:
                                next.append(neighbor.pop())
                    else:
                        while now:
                            node = now.pop()
                            if visited[node-1] == True:
                                continue
                            visited[node-1] = True
                            neighbor = copy.deepcopy(nodes[node])
                            if depth == 2 and len(neighbor) > 1:
                                even_special = node
                                # continue
                            elif baisuu1 <= n:
                                ans[node-1] = str(baisuu1)
                                baisuu1 += 3
                            else:
                                ans[node-1] = str(baisuu)
                                baisuu += 3
                            while neighbor:
                                next.append(neighbor.pop())
                    now = copy.deepcopy(next)
                    if not now:
                        break
                    next = deque()
            if baisuu2 <= n:
                ans[even_special-1] = str(baisuu2)
            else:
                ans[even_special-1] = str(baisuu)
            print(' '.join(ans))
        else:
            if round((n-1)/3) > (n-odd_num):
                print(-1)
                exit()
            else:
                while True:
                    odd = not odd
                    depth += 1
                    if not odd:
                        while now:
                            node = now.pop()
                            if visited[node-1] == True:
                                continue
                            visited[node-1] = True
                            neighbor = copy.deepcopy(nodes[node])
                            if baisuu2 <= n:
                                ans[node-1] = str(baisuu2)
                                baisuu2 += 3
                            else:
                                ans[node-1] = str(baisuu)
                                baisuu += 3
                            while neighbor:
                                next.append(neighbor.pop())
                    else:
                        while now:
                            node = now.pop()
                            if visited[node-1] == True:
                                continue
                            visited[node-1] = True
                            neighbor = copy.deepcopy(nodes[node])
                            if len(neighbor) > 1:
                                even_special = node
                                # continue
                            elif baisuu1 <= n:
                                ans[node-1] = str(baisuu1)
                                baisuu1 += 3
                            else:
                                ans[node-1] = str(baisuu)
                                baisuu += 3
                            while neighbor:
                                next.append(neighbor.pop())
                    now = copy.deepcopy(next)
                    if not now:
                        break
                    next = deque()
            if baisuu2 <= n:
                ans[even_special-1] = str(baisuu2)
            else:
                ans[even_special-1] = str(baisuu)
            print(' '.join(ans))

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 = {i: {d: [] for d in range(4)} for i in range(1, N + 1)}
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()
        if d > 3:
            break
        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 (rest[1] or rest[2]):
        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:
from collections import deque

N = int(input())
grid = [[] for _ in range(N+1) ]

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

def distance(p):
  not_3 = set([p])
  first = grid[p]
  second = []
  for i in first:
    not_3.add(i)
    second.append(i)
      
  third = set()
  for i in second:
    for s in grid[i]:
      if s in not_3:
        continue
      third.add(s)
      not_3.add(s)
  #print(third)
  
  fourth = set()
  for i in third:
    for t in grid[i]:
      if t in not_3:
        continue
      if t > i:
        fourth.add(t)
  #print(fourth)
  return fourth 
  
ans = [-1]* (N+1)
lst_1 = deque([i+1 for i in range(N) if (i+1) % 3 == 1])
lst_2 = deque([i+1 for i in range(N) if (i+1) % 3 == 2])
lst_3 = deque([i+1 for i in range(N) if (i+1) % 3 == 0])
flg = 1
for i in range(1, N+1):
  d = distance(i)
  if d:
    p = ans[i]
    if p == -1:
      if lst_3:
        p = lst_3.popleft()
        ans[i] = p
      else:
        if flg == 1:
          p = lst_1.popleft()
          flg = 2
        else:
          p = lst_2.popleft()
          flg = 1
        ans[i] = p
    for d_ in d:
      if ans[d_] == -1:
        if p%3 == 0:
          if flg == 1:
            ans[d_] = lst_1.popleft()
            flg = 2
          else:
            ans[d_] = lst_2.popleft()
            flg = 1
        elif p%2 == 0:
          ans[d_] = lst_1.popleft()
        else:
          ans[d_] = lst_2.popleft()
          
#print(ans[1:])
for i in ans[1:]:
  if i == -1:
    if lst_1:
      print(lst_1.popleft())
    elif lst_2:
      print(lst_2.popleft())
    else:
      print(lst_3.popleft())
  else:
    print(i)

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
t = [list(map(int, input().split())) for i in range(n-1)]

def bfs(s, q):
    t = [None for i in range(n)]
    p = deque()
    t[s] = 0
    p.append(s)
    while p:
        now = p.popleft()
        next = d[now]#隣接リストを参照
        for di in next:
            if t[di] == None:
                t[di] = t[now] + 1
                if t[di] == 3:
                    q.append((s+1,di+1))
                else:
                    p.append(di)
    print(t)

#隣接リスト
d = [[] for i in range(n)]
for i in range(n-1):
    x,y = t[i]
    d[x-1].append(y-1)
    d[y-1].append(x-1)
q = deque()

for i in range(n):
    bfs(i, q)

#print(q, sep='\n')
if len(q) == 0:
    print(-1)
    exit()

ans = [i+1 for i in range(n)]
chk = [False for i in range(n)]

while q:
    now = q.popleft()
    if (ans[now[0]] + ans[now[1]])%3 == 0 or (ans[now[0]]+ans[now[1]])%3 == 0:
        chk[now[0]] = True
        chk[now[1]] = True
        pass
    else:
        if not chk[now[0]]:
            for i in range(n):
                if not chk[i]:
                    ans[now[0]], ans[i] = ans[i], ans[now[0]]
                    if (ans[now[0]] + ans[i])%3 == 0 or (ans[now[0]]+ans[i])%3 == 0:
                        chk[now[0]] = True
                        chk[i] = True
                        pass
                    else:
                        ans[i], ans[now[0]] = ans[now[0]], ans[i]
        elif not chk[now[0]]:
            for i in range(n):
                if not chk[i]:
                    ans[now[1]], ans[i] = ans[i], ans[now[1]]
                    if (ans[now[1]] + ans[i])%3 == 0 or (ans[now[1]]+ans[i])%3 == 0:
                        chk[now[1]] = True
                        chk[i] = True
                        pass
                    else:
                        ans[i], ans[now[1]] = ans[now[1]], ans[i]
        else:
            print(-1)
            exit()

print(*ans, sep=" ")

Submission status: Runtime Error

Solution code:
from collections import deque


n = int(input())

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


root = 0
visited = [-1] * n
def dfs(root):
    q = deque([root])
    visited[root] = 0
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v] != -1:
                continue
            else:
                visited[nxt_v] = (visited[v] + 1) % 2
                q.append(nxt_v)
dfs(0)
cnt0 = 0
cnt1 = 0
for i in range(n):
    if visited[i] == 0:
        cnt0 += 1
    else:
        cnt1 += 1

num1 = n // 3 
num2 = n // 3
num3 = n // 3
if n % 3 >= 1:
   num1 += 1
if n % 3 >= 2:
   num2 += 1
    
ans = [0] * n

set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
    if i % 3 == 0:
        set3.add(i)
    elif i % 3 == 1:
        set1.add(i)
    elif i % 3 == 2:
        set2.add(i)
        
if cnt0 <= num3:
    for i in range(n):
        if visited[i] == 0:
            ans[i] = pop.set3()
        else:
            if set1:
                ans[i] = pop.set1() 
            elif set2:
                ans[i] = pop.set2()         
            elif set3:
                ans[i] = pop.set3()  

elif cnt1 <= num3:
    for i in range(n):
        if visited[i] == 1:
            ans[i] = pop.set3()
        else:
            if set1:
                ans[i] = pop.set1() 
            elif set2:
                ans[i] = pop.set2()         
            elif set3:
                ans[i] = pop.set3()  
else:
    num147 = 0
    num258 = 0
    num369 = 0
    for i in range(n):
        if visited[i] == 0:
            num = num147 * 3 + 1
            if num > n:
                num = num369 * 3 + 3
                ans[i] = num
                if num > n:
                    error
                    exit()
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num # 1, 4, 7, 10, ...
            set1.remove(num)
            num147 += 1
        else:
            num = num258 * 3 + 2 
            if num > n:
                num = num369 * 3 + 3
                if num > n:
                    error
                    exit()
                ans[i] = num
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num # 2, 5, 8, 11, ...
            set2.remove(num)
            num258 += 1
     
    for i in range(n):
        if ans[i] == 0:
            if set1:
                ans[i] = set1.pop()
            elif set2:
                ans[i] = set2.pop()
            elif set3:
                ans[i] = set3.pop()
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
t = [list(map(int, input().split())) for i in range(n-1)]

def bfs(s, q):
    t = [None for i in range(n)]
    p = deque()
    t[s] = 0
    p.append(s)
    while p:
        now = p.popleft()
        next = d[now]#隣接リストを参照
        for di in next:
            if t[di] == None:
                t[di] = t[now] + 1
                if t[di] == 3:
                    q.append((s+1,di+1))
                else:
                    p.append(di)
    print(t)

#隣接リスト
d = [[] for i in range(n)]
for i in range(n-1):
    x,y = t[i]
    d[x-1].append(y-1)
    d[y-1].append(x-1)
q = deque()

for i in range(n):
    bfs(i, q)

#print(q, sep='\n')
if len(q) == 0:
    print(-1)
    exit()

ans = [i+1 for i in range(n)]
chk = [False for i in range(n)]

while q:
    now = q.popleft()
    if (ans[now[0]] + ans[now[1]])%3 == 0 or (ans[now[0]]+ans[now[1]])%3 == 0:
        chk[now[0]] = True
        chk[now[1]] = True
        pass
    else:
        if not chk[now[0]]:
            for i in range(n):
                if not chk[i]:
                    ans[now[0]], ans[i] = ans[i], ans[now[0]]
                    if (ans[now[0]] + ans[i])%3 == 0 or (ans[now[0]]+ans[i])%3 == 0:
                        chk[now[0]] = True
                        chk[i] = True
                        pass
                    else:
                        ans[i], ans[now[0]] = ans[now[0]], ans[i]
        else:
            for i in range(n):
                if not chk[i]:
                    ans[now[1]], ans[i] = ans[i], ans[now[1]]
                    if (ans[now[1]] + ans[i])%3 == 0 or (ans[now[1]]+ans[i])%3 == 0:
                        chk[now[1]] = True
                        chk[i] = True
                        pass
                    else:
                        ans[i], ans[now[1]] = ans[now[1]], ans[i]
print(*ans, sep=" ")