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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n = int(input())
    l_hen = [tuple(map(int, input().split())) for _ in range(n-1)]

    def dfs(node_num,dis,pre,org):
        if dis == 2:
            for hena, henb in l_hen:
                if hena == node_num and henb != pre:
                    combi.append((min(org, henb), max(org, henb)))
                elif henb == node_num and hena != pre:
                    combi.append((min(org, hena), max(org, hena)))
        else:
            for hena, henb in l_hen:
                if hena == node_num and henb != pre:
                    dfs(henb, dis + 1, node_num,org)
                elif henb == node_num and hena != pre:
                    dfs(hena, dis + 1, node_num,org)


    combi = []
    for node in range(1, n+1):
        for hena, henb in l_hen:
            if hena == node:
                dfs(henb, 1, node,node)
            elif henb == node:
                dfs(hena, 1, node,node)
    combi = set(combi)
    combi = list(combi)

    list1 = [0 for _ in range(n+1)]
    list2 = [0 for _ in range(n+1)]
    # まず「組」それぞれの片方を３の倍数の位置におく。置いたら組の片割れが未配置ならひとつ前の位置に置く。
    for i in range(1, (n // 3)+1):
        com_a, com_b = combi[i]
        if not list2[com_a]:
            list1[i * 3] = com_a
            list2[com_a] = i * 3
            if not list2[com_b]:
                list1[i * 3 - 1] = com_b
                list2[com_b] = i * 3 -1
        elif not list2[com_b]:
            list1[i * 3] = com_b
            list2[com_b] = i * 3
            if not list2[com_a]:
                list1[i * 3 -1] = com_a
                list2[com_a] = i * 3 - 1

    # 「組」の未配置のものを配置する
    for com_a, com_b in combi:
        # 組のどちらかが配置済みだったら

        if (list2[com_a] and not list2[com_b]) or (not list2[com_a] and list2[com_b]):
            if list2[com_a] and not list2[com_b]:
                for k in range(1, n+1):
                    if not list2[com_b] and k != list2[com_a] and not list1[k] and (k * list2[com_a]) % 3 == 0:
                        list1[k] = com_b
                        list2[com_b] = k
                    elif not list2[com_a] and k != list2[com_a] and not list1[k] and (k + list2[com_a]) % 3 == 0:
                        list1[k] = com_b
                        list2[com_b] = k
            elif not list2[com_a] and list2[com_b]:
                for k in range(1, n+1):
                    if  k != list2[com_b] and not list1[k] and (k * list2[com_b]) % 3 == 0:
                        list1[k] = com_a
                        list2[com_a] = k
                    elif k != list2[com_b] and not list1[k] and (k + list2[com_b]) % 3 == 0:
                        list1[k] = com_a
                        list2[com_a] = k
        # 組の両方とも未配置だったら
        elif not list2[com_a] and not list2[com_b]:

            for j in range(1,n+1):
                for l in range(1,n+1):
                    if not list1[j] and not list1[l] and (j + l) %3 == 0:
                        list1[j] = com_a
                        list1[l] = com_b
                        list2[com_a] = j
                        list2[com_b] = l
                    elif not list1[j] and not list1[l] and (j * l) %3 == 0:
                        list1[j] = com_a
                        list1[l] = com_b
                        list2[com_a] = j
                        list2[com_b] = l
                    else:
                        print(-1)
                        exit()


    for m in range(1, n+1):
        if not list2[m]:
            for o in range(1, n+1):
                if not list1[o]:
                    list1[o] = m
                    list2[m] = o
                    break
    del(list2[0])
    if all(list2):
        for i in range(1, n+1):
            print(list1[i], end=' ')
    else:
        print(-1)

        if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
n = int(readline())

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)

colors = [0] * (n+1)
 
colors[1] = 1
 
todo = []
for to in g[1]:
    todo.append([to, -1])
 
while todo:
    node, color = todo.pop()
 
    if colors[node] != 0:
        continue
 
    colors[node] = color
    new_color = -color
    for to in g[node]:
        if colors[to] != 0:
            continue
        todo.append([to, new_color])
ans = [0]*(n+1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1,n+1):
    if i%3==1:
        t1.append(i)
    elif i%3==2:
        t2.append(i)
    else:
        t0.append(i)
black = 0
for i in colors[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if colors[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
elif black > n-n//3:
    for i in range(1,n+1):
        if colors[i] == -1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if colors[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for i in range(1, N + 1):
    if i % 3 == 0:
        mod0.append(i)
    elif i % 3 == 1:
        mod1.append(i)
    else:
        mod2.append(i)

dist = [-1] * (N + 1)


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even < N // 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd < N // 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for i in range(1, N + 1):
    modfit(i)

print()

Submission status: Runtime Error

Solution code:

#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict, deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def dfs(node, depths, d, connected, parent):
	depths[node-1]=d
	for child in connected[node]:
		if child==parent: continue
		dfs(child, depths, not d, connected, node)
		

def main(inputs):
	n=int(inputs[0][0])
	
	edge=defaultdict(list)
	for i in range(n-1):
		a,b=getIntList(inputs[1+i])
		edge[a].append(b)
		edge[b].append(a)
	
	depths=np.empty(n, np.bool)
	dfs(1, depths, 0, edge, -1)
# 	print(depths)
# 	depths%=2
	
	m=n%3
	if m==0: remainingMod=[n//3,n//3,n//3]
	elif m==1: remainingMod=[n//3,n//3+1,n//3]
	elif m==2: remainingMod=[n//3,n//3+1,n//3+1]
# 	print(remainingMod)
	
	values=np.empty(n, int8)
	sum0=(depths==0).sum()
	sum1=(depths==1).sum()
	if sum0<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=sum0
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==1]=remaining
	
	elif sum1<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=sum1
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==0]=remaining
		
	else:
		index0=np.where(depths==0)[0]
		index1=np.where(depths==1)[0]
		
		values[index0[:remainingMod[1]]]=1
		values[index1[:remainingMod[2]]]=2
		
		values[index0[remainingMod[1]:]]=0
		values[index1[remainingMod[2]:]]=0

	values[values==0]=np.arange(remainingMod[0])*3+3
	values[values==1]=np.arange(remainingMod[1])*3+1
	values[values==2]=np.arange(remainingMod[2])*3+2
	print(" ".join(map(str,values)))

# 	v3=defaultdict(list)
# 	for i in range(1,n+1):
# 		visited=set([i])
# 		prev=[i]
# 		for count in range(3):
# 			next=[]
# 			for node in prev:
# 				for child in edge[node]:
# 					if child in visited: continue
# 					next.append(child)
# 			visited.update(next)
# 			prev=next
# # 			print(i, next)
# 		v3[i]=next
# 	
# 	print("testing")
# 	for v0 in v3:
# 		for v1 in v3[v0]:
# 			val0=values[v0-1]
# 			val1=values[v1-1]
# 			if (val0+val1)%3==0 or (val0*val1)%3==0:
# 				print(v0, val0, v1, val1, "ok")
# 			else:
# 				print(v0, val0, v1, val1, "NG")
		
	


if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for i in range(1, N + 1):
    if i % 3 == 0:
        mod0.append(i)
    elif i % 3 == 1:
        mod1.append(i)
    else:
        mod2.append(i)

dist = [-1] * (N + 1)


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even < N / 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd < N / 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for i in range(1, N + 1):
    modfit(i)

print()

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
from collections import deque
l = [deque() for _ in range(N+1)]
ans = [0]*N
for a,b in ab:
  l[a].append(b)
  l[b].append(a)
  
r = [0]*(N+1)
i = 0
p = l[1]
q = deque()
flag = [False]*(N+1)
flag[1]=True
while (len(p)!=0)or(len(q)!=0):
  if i%2==0:
    while len(p)!=0:
      j = p.pop()
      if flag[j]:
        continue
      else:
        q.extend(l[j])
        flag[j]=True
        r[j]=1
    i+=1
  else:
    i+=1
    while len(q)!=0:
      j = q.pop()
      if flag[j]:
        continue
      else:
        p.extend(l[j])
        flag[j]=True
a = deque(range(1,N+1,3))
b = deque(range(2,N+1,3))
c = deque(range(3,N+1,3))
x = sum(r)
if x<=N//3:
  for i in range(1,N+1):
    if r[i]==1:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      else:
        ans[i-1]=b.pop()
elif (N-x)<=N//3:
  for i in range(1,N+1):
    if r[i]==0:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      else:
        ans[i-1]=b.pop()
else:
  for i in range(1,N+1):
    if r[i]==1:
      if len(a)!=0:
        ans[i-1]=a.pop()
      else:
        ans[i-1]=c.pop()
    else:
      if len(b)!=0:
        ans[i-1]=b.pop()
      else:
        ans[i-1]=c.pop()
        
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10000000)
readline = sys.stdin.buffer.readline
n = int(readline())

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)

colors = [0] * (n+1)
 
colors[1] = 1
 
todo = []
for to in g[1]:
    todo.append([to, -1])
 
while todo:
    node, color = todo.pop()
 
    if colors[node] != 0:
        continue
 
    colors[node] = color
    new_color = -color
    for to in g[node]:
        if colors[to] != 0:
            continue
        todo.append([to, new_color])
ans = [0]*(n+1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1,n+1):
    if i%3==1:
        t1.append(i)
    elif i%3==2:
        t2.append(i)
    else:
        t0.append(i)
black = 0
for i in colors[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if colors[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if colors[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])

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 i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

class TREE(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()
        # self.doubling()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]


depth = TREE(es).depth

ans = [0]*n

zero = one = two = n // 3
if n % 3 == 1: one += 1
if n % 3 == 2:
    one+=1
    two+=1


for i in range(n):
    if depth[i] % 2 == 0:
        if one > 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
else:
    print(*ans, sep=' ')
    exit()

zero = one = two = n // 3
if n % 3 == 1: one += 1
if n % 3 == 2:
    one+=1
    two+=1

for i in range(n):
    if depth[i] % 2 == 1:
        if one > 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
else:
    print(*ans, sep=' ')
    exit()

raise Exception('Error!')

Submission status: Runtime Error

Solution code:

#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict, deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def dfs(node, depths, d, connected, parent):
	depths[node-1]=d
	for child in connected[node]:
		if child==parent: continue
		dfs(child, depths, not d, connected, node)
		

def main(inputs):
	n=int(inputs[0][0])
	
	edge=defaultdict(list)
	for i in range(n-1):
		a,b=getIntList(inputs[1+i])
		edge[a].append(b)
		edge[b].append(a)
	
	depths=np.empty(n, np.bool)
	dfs(1, depths, 0, edge, -1)
# 	print(depths)
# 	depths%=2
	
	m=n%3
	if m==0: remainingMod=[n//3,n//3,n//3]
	elif m==1: remainingMod=[n//3,n//3+1,n//3]
	elif m==2: remainingMod=[n//3,n//3+1,n//3+1]
# 	print(remainingMod)
	
	values=np.empty(n, int8)
	if (depths==0).sum()<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=(depths==0).sum()
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==1]=remaining
	
	elif (depths==1).sum()<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=(depths==1).sum()
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==0]=remaining
		
	else:
		index0=np.where(depths==0)[0]
		index1=np.where(depths==1)[0]
		
		values[index0[:remainingMod[1]]]=1
		values[index1[:remainingMod[2]]]=2
		
		values[index0[remainingMod[1]:]]=0
		values[index1[remainingMod[2]:]]=0

	nextValue=[3,1,2]
	for i,v in enumerate(values):
		v3=v%3
		values[i]=nextValue[v3]
		nextValue[v3]+=3
	print(" ".join(map(str,values)))

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

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

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for i in range(1, N + 1):
    if i % 3 == 0:
        mod0.append(i)
    elif i % 3 == 1:
        mod1.append(i)
    else:
        mod2.append(i)

dist = [-1] * (N + 1)


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N // 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N // 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for i in range(1, N + 1):
    modfit(i)

print()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for i in range(1, N + 1):
    if i % 3 == 0:
        mod0.append(i)
    elif i % 3 == 1:
        mod1.append(i)
    else:
        mod2.append(i)

dist = [-1] * (N + 1)


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N // 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N // 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for i in range(1, N + 1):
    modfit(i)

print()

Submission status: Runtime Error

Solution code:

#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict, deque

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def dfs(node, depths, d, connected, parent):
	depths[node-1]=d
	for child in connected[node]:
		if child==parent: continue
		dfs(child, depths, d+1, connected, node)
		

def main(inputs):
	n=int(inputs[0][0])
	
	edge=defaultdict(list)
	for i in range(n-1):
		a,b=getIntList(inputs[1+i])
		edge[a].append(b)
		edge[b].append(a)
	
	depths=np.empty(n, int32)
	dfs(1, depths, 0, edge, -1)
# 	print(depths)
	depths%=2
	
	m=n%3
	if m==0: remainingMod=[n//3,n//3,n//3]
	elif m==1: remainingMod=[n//3,n//3+1,n//3]
	elif m==2: remainingMod=[n//3,n//3+1,n//3+1]
# 	print(remainingMod)
	
	values=np.empty(n, int8)
	if (depths==0).sum()<=remainingMod[0]:
		values[depths==0]=0
		remainingMod[0]-=(depths==0).sum()
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==1]=remaining
	
	elif (depths==1).sum()<=remainingMod[0]:
		values[depths==1]=0
		remainingMod[0]-=(depths==1).sum()
		remaining=np.concatenate([v*np.ones(remainingMod[v], int8) for v in range(3)])
		values[depths==0]=remaining
		
	else:
		index0=np.where(depths==0)[0]
		index1=np.where(depths==1)[0]
		
		values[index0[:remainingMod[1]]]=1
		values[index1[:remainingMod[2]]]=2
		
		values[index0[remainingMod[1]:]]=0
		values[index1[remainingMod[2]:]]=0

	nextValue=[3,1,2]
	for i,v in enumerate(values):
		v3=v%3
		values[i]=nextValue[v3]
		nextValue[v3]+=3
	print(" ".join(map(str,values)))

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for i in range(1, N + 1):
    if i % 3 == 0:
        mod0.append(i)
    elif i % 3 == 1:
        mod1.append(i)
    else:
        mod2.append(i)

dist = [-1] * (N + 1)


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N // 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N // 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for i in range(1, N + 1):
    modfit(i)

print()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10000000)
readline = sys.stdin.buffer.readline
n = int(readline())

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)

color = [0] * (n+1) #color[i]:点iの色(1 or -1)。但し塗られていないときは0とする

def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(g[v])):
        if color[ g[v][i] ] == 0:
            f(g[v][i],-c)
ans = [0]*(n+1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1,n+1):
    if i%3==1:
        t1.append(i)
    elif i%3==2:
        t2.append(i)
    else:
        t0.append(i)
res = f(i,1)
black = 0
for i in color[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if color[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if color[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for i in range(1, N + 1):
    if i % 3 == 0:
        mod0.append(i)
    elif i % 3 == 1:
        mod1.append(i)
    else:
        mod2.append(i)

dist = [-1] * (N + 1)


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N // 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N // 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for i in range(1, N + 1):
    modfit(i)
    print(node_p[i], end=" ")

print()