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:
class Tree:
    def __init__(self, N):
        self.N = N # #vertices
        self.D = (self.N-1).bit_length() # #iterations in doubling
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def lca_initialize(self):
        self.dfs(0)
        self.doubling()
    
    def dfs(self, root):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the root.
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)
    
    def doubling(self):
        # O(N log N) time
        self.next = [[-1] * self.N for _ in range(self.D)]
        for v in range(self.N):
            self.next[0][v] = self.parent[v]
        for d in range(self.D - 1):
            for v in range(self.N):
                if self.next[d][v] != -1:
                    self.next[d + 1][v] = self.next[d][self.next[d][v]]
    
    def lca(self, u, v):
        # O(log N) time
        # the depth of v is set to be no less than that of u
        if self.depth[u] > self.depth[v]: u, v = v, u
        # find the ancestor of v with the same depth as that of u
        diff = self.depth[v] - self.depth[u]
        for i in range(diff.bit_length()):
            if diff & (1 << i): v = self.next[i][v]
        if u == v: return u
        for i in range(self.depth[u].bit_length() - 1, -1, -1):
            pu, pv = self.next[i][u], self.next[i][v]
            if pu != pv: u, v = pu, pv
        return self.next[0][u]

N = int(input())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(0)
d_odd, d_even = [], []
rem = [[] for _ in range(3)]
for i in range(N):
    if tr.depth[i] % 2 == 0: d_even.append(i)
    else: d_odd.append(i)
    rem[(i+1)%3].append(i+1)
P = [0] * N
if len(d_odd) < len(d_even):
    for i in d_odd:
        if rem[2]:
            P[i] = rem[2].pop()
        elif rem[0]:
            P[i] = rem[0].pop()
        else:
            P[i] = rem[1].pop()
    temp = rem[0] + rem[1]
    for i in d_even: P[i] = temp.pop()
else:
    for i in d_even:
        if rem[2]:
            P[i] = rem[2].pop()
        elif rem[0]:
            P[i] = rem[0].pop()
        else:
            P[i] = rem[1].pop()
    temp = rem[0] + rem[1]
    for i in d_odd: P[i] = temp.pop()
print(*P)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
graph = {i:[] for i in range(n)}
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
  
one = n//3 + bool(n%3)
two = n//3 + bool(n%3>1)
three = n//3
nums = [three+1,one,two]
perms = [0 for i in range(n)]



def dfs(i,n):
  global nums
  perms[i] = (nums[n]-1)*3 + n
  nums[n] -= 1 
  for node in graph[i]:
    if perms[node] == 0:
      next_n = (3-n)%3
      if nums[next_n] == 0:
        dfs(node,0)
      else:
        dfs(node,next_n)

dfs(0,1)
print(*perms)

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)
  
#print(grid)

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

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
visited = [False]*N
q = deque([0])  # 始まりのノード
visited[0] = True
distant = [0]*N
distant[0] = 0
while len(q):
    # vは数字, 親のノードのインデックス
    v = q.pop()
    color = 1

    for e in tree[v]:
        if visited[e]:  # 到達済みなら次のノードへ
            continue
        visited[e] = True
        distant[e] = (distant[v] + 1) % 3
        q.append(e)

mod_dict = defaultdict(deque)
for i in range(2, N+1):
    mod_dict[i%3].append(i)
# print(mod_dict)
ans = [1]
for i in range(1, N):
    if len(mod_dict[distant[i%3]]) > 0:
        ans.append(mod_dict[distant[i]].popleft())
    elif len(mod_dict[distant[0]]) > 0:
        ans.append(mod_dict[distant[0]].popleft())
    else:
        print('-1')
        exit()
print(" ".join(map(str, ans)))

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)]
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(3)] for _ in range(6)]
for i,d in enumerate(depth):
    if d%3==0:
        mem[0][0].append(i)
        mem[3][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[0][1].append(i)
            mem[3][2].append(i)
        else:
            mem[0][2].append(i)
            mem[3][1].append(i)
    else:
        if (d//3)%2:
            mem[0][2].append(i)
            mem[3][1].append(i)
        else:
            mem[0][1].append(i)
            mem[3][2].append(i)
    d -= 1
    if d%3==0:
        mem[1][0].append(i)
        mem[4][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[1][1].append(i)
            mem[4][2].append(i)
        else:
            mem[1][2].append(i)
            mem[4][1].append(i)
    else:
        if (d//3)%2:
            mem[1][2].append(i)
            mem[4][1].append(i)
        else:
            mem[1][1].append(i)
            mem[4][2].append(i)
    d -= 1
    if d%3==0:
        mem[2][0].append(i)
        mem[5][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[2][1].append(i)
            mem[5][2].append(i)
        else:
            mem[2][2].append(i)
            mem[5][1].append(i)
    else:
        if (d//3)%2:
            mem[2][2].append(i)
            mem[5][1].append(i)
        else:
            mem[2][1].append(i)
            mem[5][2].append(i)

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

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)

last = set(range(1, N + 1))
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
        result[self.v] = last.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()

# ---
group = [[], [], []]
for node in nodes.values():
    group[node.rank % 3].append(node)
group.sort(key=len)
indexes = [0] * 3
result = {}
for node in group[0]:
    indexes[0] += 1
    result[node.v] = indexes[0] * 3
    last.remove(indexes[0] * 3)
for node in group[1]:
    if indexes[1] >= N // 3 + ((N % 3) >= 1):
        indexes[0] += 1
        result[node.v] = indexes[0] * 3
        last.remove(indexes[0] * 3)
    else:
        result[node.v] = indexes[1] * 3 + 1
        last.remove(indexes[1] * 3 + 1)
        indexes[1] += 1
for node in group[2]:
    result[node.v] = last.pop()
#
#     result[node.v] = indexes[2] * 3 + 2
#     indexes[2] += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n-1)]

V = [0] * (n+1)
PP = [[] for i in range(n+1)]

M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

# 1始まりの場合
Q = [[1,-1,-1]]
s = 0
V[1] = 1
while s < len(Q):
    i = Q[s][0]
    p = Q[s][1]
    pp = Q[s][2]
    if pp >= 0:
        for y in M[pp]:
            if y != p:
                PP[y].append(i)
                PP[i].append(y)

    for x in M[i]:
        if V[x] == 0:
            V[x] = 1
            Q.append([x, i, p])
    s += 1
# print(PP)
vv = -1
V = [0] * (n+1)
for i in range(len(PP)):
    if len(PP[i]) == 0:
        vv += 1
        V[i] = 1
# print(vv)
mi = vv

J = [n//3 for i in range(3)]
if n%3==1:
    J[1] += 1
elif n%3==2:
    J[1] += 1
    J[2] += 1
# print(J)
# J[1] = max(0, J[1] - vv//2)
# J[2] = max(0, J[2] - vv//2)
# if vv%2==1:
#     J[1] = max(0, J[1] - 1)
# print(J)

# print("V",V)
r = -1
R = [[], []]
QQ = [[] for i in range(n+1)]
for ii in range(n+1):
    if V[ii] == 0:
        r += 1
        Q = [[ii,-1]]
        s = 0
        V[ii] = 1
        while s < len(Q):
            # print(Q)
            i = Q[s][0]
            p = Q[s][1]
            if p >= 0:
                for y in PP[p]:
                    if y != i:
                        QQ[y].append(i)
                        R[r].append(y)
                        # QQ[i].append(y)

            for x in PP[i]:
                if V[x] == 0:
                    V[x] = 1
                    Q.append([x, i])
            s += 1

# print(QQ)
R = [list(set(R[i])) for i in range(2)]
if len(R[1]) > len(R[0]):
    R = [R[1], R[0]]

# print(R)
if max(0, J[1]-len(R[0])) + max(0, J[2]-len(R[1])) <= mi:
    ANS = [-1] * n
    for i in R[0]:
        ANS[i-1] = 1
        J[1] -= 1
    for i in R[1]:
        ANS[i-1] = 2
        J[2] -= 1
    tt = 0
    for i in range(len(ANS)):
        if ANS[i] == -1:
            while J[tt] == 0:
                tt += 1
            ANS[i] = tt
            J[tt] -= 1

    # print(ANS)

    K = [1,0,0]
    for i in range(len(ANS)):
        ANS[i] += K[ANS[i]%3] * 3
        K[ANS[i]%3] += 1
    # print(ANS)
    print(" ".join([str(i) for i in ANS]))
else:
    print(-1)

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)
  
#print(grid)

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
      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:
import sys
input = sys.stdin.readline
from collections import deque
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)

    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])])]
    # 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)]
    ANS = [0]*N
    for i in range(3):
        x = i
        y = i+3
        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:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline

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

edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

E = [0] * N

for s in range(N):
    que = deque([(s, 0)])
    V = set()
    T = set()
    while que:
        now, depth = que.pop()
        V.add(now)

        if depth == 3:
            T.add(now)
            continue

        for to in edges[now]:
            if not to in V:
                que.append((to, depth + 1))
    E[s] = (s, T)

ans = [-1] * N
now = 3
canUse = set(range(1, N + 1))
V = set()
for s, T in E:
    if len(T - V) <= 1:
        continue
    ans[s] = now
    canUse.remove(now)
    V.add(s)
    now += 3

canUse = deque(canUse)
for i, a in enumerate(ans):
    if a != -1:
        continue
    ans[i] = canUse.pop()

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
l = [[0] * N for i in range(N)]

eda = []
for i in range(N-1):
    tmp = LIST()
    tmp = [int(t) for t in tmp]
    eda.append(tmp)
for e in eda:
    l[e[0]-1][e[1]-1] = 1
    l[e[1]-1][e[0]-1] = 1
kyori = shortest_path(csr_matrix(l))

ans = []
for i in range(len(kyori[0])):
    for j in range(i+1, len(kyori[0])):
        if kyori[i][j] == 3:
            tmp = [i, j]
            ans.append(tmp)

p = [1] * N
for a in ans:
    p[a[0]] = 3
    p[a[1]] = 3
print(p)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, a: "List[int]", b: "List[int]"):
    mat = [[] for _ in range(N+1)]

    for i in range(N-1):
        mat[a[i]].append(b[i])
        mat[b[i]].append(a[i])
    
    # 各頂点から距離3の頂点を格納、ただし自分より大きいもの
    dist_three = [[] for _ in range(N+1)]

    for root in range(1,N+1):
        queue = deque([(root,0)])
        isVisited = [False]*(N+1)
        while queue:
            node,count = queue.popleft()
            if count == 3 and root < node:
                dist_three[root].append(node)
            elif count == 4:
                break
            isVisited[node] = True

            for next in mat[node]:
                if isVisited[next]:
                    continue
                queue.append((next,count+1))

    answer = [0]*(N+1)

    multiple_three = []
    mod1_num = []
    mod2_num = []
    for i in range(1,N+1):
        if i%3==0:
            multiple_three.append(i)
        elif i%3==1:
            mod1_num.append(i)
        else:
            mod2_num.append(i)
    all_num = set(range(1,N+1))

    for i in range(1,N+1):
        if not dist_three[i]:
            continue
        if dist_three[i] and multiple_three:
            answer[i] = multiple_three.pop()
        elif dist_three[i] and not multiple_three:
            if len(mod1_num) > len(dist_three[i]):
                answer[i] = mod2_num.pop()
                for next_node in dist_three[i]:
                    answer[next_node] = mod1_num.pop()
            else:
                answer[i] = mod1_num.pop()
                for next_node in dist_three[i]:
                    answer[next_node] = mod2_num.pop()
        
    amari_num = list(all_num-set(answer))

    for i in range(1,N+1):
        if answer[i]==0:
            answer[i] = amari_num.pop()

    print(*answer[1:])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

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

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

group = [[], [], []]
for node in nodes.values():
    group[node.rank % 3].append(node)
group.sort(key=len)
indexes = [0] * 3
result = {}
last = set(range(1, N + 1))
for node in group[0]:
    indexes[0] += 1
    result[node.v] = indexes[0] * 3
    last.remove(indexes[0] * 3)
for node in group[1]:
    if indexes[1] >= N // 3 + ((N % 3) >= 1):
        indexes[0] += 1
        result[node.v] = indexes[0] * 3
        last.remove(indexes[0] * 3)
    else:
        result[node.v] = indexes[1] * 3 + 1
        last.remove(indexes[1] * 3 + 1)
        indexes[1] += 1
for node in group[2]:
    result[node.v] = last.pop()
#
#     result[node.v] = indexes[2] * 3 + 2
#     indexes[2] += 1
print(' '.join(str(result[i]) for i in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
# 0-2: amari
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(step, idx, pre_3, pre_2, pre_1):
    pre_3_mod = pre_3 % 3
    if pre_3 == -1:
        if len(nums[step%3]) > 0:
            out = nums[step%3].pop()
        else:
            for i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    out = nums[i].pop()
                    break
    else:
        if pre_3_mod != 0:
            if len(nums[3 - (pre_3_mod)]) > 0:
                out = nums[3 - (pre_3_mod)].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(ans)
                    print(-1)
                    exit()
        else:
            if len(nums[1]) > len(nums[2]):
                out = nums[1].pop()
            else:
                out = nums[2].pop()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(step+1, k, pre_2, pre_1, out)

dfs(1, 1, -1, -1, -1)

print(" ".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline

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

edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

E = [0] * N

for s in range(N):
    que = deque([(s, 0)])
    visited = [False] * N
    T = set()
    while que:
        now, depth = que.pop()
        visited[now] = True

        if depth == 3:
            T.add(now)
            continue

        for to in edges[now]:
            if not visited[to]:
                que.append((to, depth + 1))
    E[s] = (s, T)
E.sort(key=lambda a: len(a[1]), reverse=True)

ans = [-1] * N

now = 3
canUse = set(range(1, N + 1))
V = set()
for s, T in E:
    if len(T) == 1:
        break
    if len(T - V) <= 1:
        continue
    ans[s] = now
    canUse.remove(now)
    V.add(s)
    now += 3

canUse = deque(canUse)
for i, a in enumerate(ans):
    if a != -1:
        continue
    ans[i] = canUse.pop()

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.buffer.readline

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

edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

E = [0] * N

for s in range(N):
    que = deque([(s, 0)])
    visited = [False] * N
    T = []
    while que:
        now, depth = que.pop()
        visited[now] = True

        if depth == 3:
            T.append(now)
            continue

        for to in edges[now]:
            if not visited[to]:
                que.append((to, depth + 1))
    E[s] = (s, T)
E.sort(key=lambda a: len(a[1]), reverse=True)

ans = [-1] * N

now = 3
canUse = set(range(1, N + 1))
for s, T in E:
    if len(T) == 1:
        break
    ans[s] = now
    canUse.remove(now)
    now += 3

canUse = deque(canUse)
for i, a in enumerate(ans):
    if a != -1:
        continue
    ans[i] = canUse.pop()

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(si):
    q = deque()
    used = set()
    q.append([si, 0])
    used.add(si)

    while len(q) > 0:
        prvi, d = q.popleft()
        if d < 2:
            for i in g[prvi]:
                if i not in used:
                    q.append([i, d + 1])
                    used.add(i)

        elif d == 2:
            for i in g[prvi]:
                if i not in used:
                    if max(si, i) not in dis3_pairs[min(si, i)]:
                        dis3_pairs[min(si, i)].add(max(si, i))

                    used.add(i)


N = int(input())
g = {i: [] for i in range(1, N + 1)}

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

dis3_pairs = {i: set() for i in range(1, N + 1)}
for n in range(1, N + 1):
    bfs(n)

sorted_dis3_pairs = sorted(dis3_pairs.items(), key=lambda x: len(x[1]), reverse=True)

mod3_0 = deque()
mod3_1 = deque()
mod3_2 = deque()
for i in range(1, N + 1):
    if i % 3 == 0:
        mod3_0.append(i)
    elif i % 3 == 1:
        mod3_1.append(i)
    else:
        mod3_2.append(i)

ans = [-1 for _ in range(N)]
for par_node, chi_nodes in sorted_dis3_pairs:
    if len(chi_nodes) == 0:
        continue

    if len(mod3_0) > 0:
        tmp_num1 = mod3_0.pop()
        ans[par_node - 1] = tmp_num1
    else:
        if len(mod3_1) > len(mod3_2):
            for_par_node = mod3_2
            for_chi_node = mod3_1
        else:
            for_par_node = mod3_1
            for_chi_node = mod3_2

        tmp_num1 = for_par_node.pop()
        ans[par_node - 1] = tmp_num1
        for chi_node in chi_nodes:
            tmp_num2 = for_chi_node.pop()
            ans[chi_node - 1] = tmp_num2

for i in range(N):
    if ans[i] == -1:
        if len(mod3_0) > 0:
            ans[i] = mod3_0.pop()
        elif len(mod3_1) > 0:
            ans[i] = mod3_1.pop()
        else:
            ans[i] = mod3_2.pop()

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
L = [-1]*n
dist = [-1]*n
dist[0] = 0
F_1 = [i for i in range(1, n+1) if i%3==1]
F_2 = [i for i in range(1, n+1) if i%3==2]
F_0 = [i for i in range(1, n+1) if i%3==0]
def dfs(v):
  if dist[v]%3==1:
    if F_1:
      L[v] = F_1.pop()
    else:
      L[v] = F_0.pop()
  elif dist[v]%3==2:
    if F_2:
      L[v] = F_2.pop()
    else:
      L[v] = F_0.pop()
  else:
    L[v] = F_0.pop()
  for nv in T[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v] + 1
      dfs(nv)
dfs(0)
print(*L)