Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.

Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

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

1\leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

If no permutation satisfies the condition, print -1.

Otherwise, print a permutation satisfying the condition, with space in between.
If there are multiple solutions, you can print any of them.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

1 2 5 4 3 

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

p_2 + p_4 = 6

p_2\times p_5 = 6

Thus, this permutation satisfies the condition.



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


Sample output:
1 2 5 4 3

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

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)]
for i in range(1, n+1):
    nums[i%3].append(i)

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 1)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    ans[i] = nums[i].pop()


if cnts[0] <= n // 3:
    solve(0)
elif cnts[1] <= n // 3:
    solve(1)
elif cnts[0] > n // 3 and cnts[1] > n // 3:
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()
else:
    print(-1)
    exit()

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

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)
"""#親のノードに子を入れてくdfs
stack = [1]
parent = [0]*(n+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in g[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)"""
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] ] == c:
            return False
        elif color[ g[v][i] ] == 0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
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:
import sys
from collections import deque
sys.setrecursionlimit(100000)
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)
"""#親のノードに子を入れてくdfs
stack = [1]
parent = [0]*(n+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in g[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)"""
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] ] == c:
            return False
        elif color[ g[v][i] ] == 0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
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:
import sys
from collections import defaultdict as dd
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)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(cl)
if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      else: res[i] = nm[2].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      else: res[i] = nm[2].pop()
  print(*res[1: ])
  exit(0)
#print(nm)
#print(cl, nm)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        f = 1
        break
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        f = 1
        break
if f:
  nm = [[] for _ in range(3)]
  for i in range(1, N + 1): nm[i % 3].append(i)
  res = [0] * (N + 1)
  for i in range(1, N + 1):
    if cl[i] == 0:
      if len(nm[1]):
        res[i] = nm[1].pop()
      else:
        if len(nm[0]):
          res[i] = nm[0].pop()
        else:
          print(-1)
          exit(0)
    else:
      if len(nm[2]):
        res[i] = nm[2].pop()
      else:
        if len(nm[0]):
          res[i] = nm[0].pop()
        else:
          print(-1)
          exit(0)
print(*res[1: ])

Submission status: Runtime Error

Solution code:
from collections import defaultdict


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

colors = [-1] * n

colors[0] = 0

todo = []
for to in edges[0]:
    todo.append([to, 1])

while todo:
    node, color = todo.pop()

    if colors[node] != -1:
        continue

    colors[node] = color
    new_color = 1 - color
    for to in edges[node]:
        if colors[to] != -1:
            continue
        todo.append([to, new_color])

red_count = sum(colors)  # 1
blue_count = n - red_count  # 0

ans = [0] * n

num3s = list(range(3, n+1, 3))
nums = [num for num in range(1, n+1) if num % 3 != 0]

if red_count <= n // 3:
    for node in range(n):
        if colors[node] == 1:
            ans[node] = num3s.pop()

        else:
            if num3s:
                num = num3s.pop()
            else:
                num = nums.pop()
            ans[node] = num


elif blue_count <= n // 3:
    for node in range(n):
        if colors[node] == 0:
            ans[node] = num3s.pop()

        else:
            if num3s:
                num = num3s.pop()
            else:
                num = nums.pop()
            ans[node] = num

else:
    num1s = list(range(1, n+1, 3))
    num2s = list(range(2, n+1, 3))
    print(1)
    exit()

    for node in range(n):
        if colors[node] == 1:
            if num1s:
                num = num1s.pop()
            else:
                num = num3s.pop()
            ans[node] = num

        else:
            if num2s:
                num = num2s.pop()
            else:
                num = num3s.pop()
            ans[node] = num

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
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)
"""#親のノードに子を入れてくdfs
stack = [1]
parent = [0]*(n+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in g[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)"""
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] ] == c:
            return False
        elif color[ g[v][i] ] == 0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
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:


#####

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(v, remaining, connected, nodes):
	nodes.append(v)
	for child in connected[v]:
		if child not in remaining: continue
		remaining.remove(child)
		dfs(child, remaining, connected, nodes)


def test(nodes, index, remainingMod, values, connected):
	node=nodes[index]
# 	print("node", node)
# 	print("values", values)
	
	possibleValues=np.array([remainingMod[v]>0 for v in range(3)], np.bool)
	ok=possibleValues.sum()>0
	if ok:
		for n1 in connected[node]:
			if n1 in values:
				if values[n1]==1:
					possibleValues[1]=False
				elif values[n1]==2:
					possibleValues[2]=False
				if possibleValues.sum()==0:
					ok=False
					break
	
# 	print("ok", ok)
	
	if not ok:
		return False
	
	for v in range(3):
		if not possibleValues[v]: continue
		values[node]=v
		remainingMod[v]-=1
		if index==len(nodes)-1:
			return True
		r=test(nodes, index+1, remainingMod, values, connected)
		if r:
			return True
		remainingMod[v]+=1
		
	values.pop(node)
	return False
		


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)
	
	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(v3)
# 	for i in v3: print(i, v3[i])
# 	print()
	connected=v3
	
	nodes=sorted(range(1, n+1), key=lambda n:-len(connected[n]))
# 	print("nodes", nodes)
	
	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("remainingMod0", remainingMod)

	values={}
	r=test(nodes, 0, remainingMod, values, connected)
	if not r:
		print("-1")
		sys.exit(0)
		
# 	print(values)
	valueList=[values[n] for n in range(1, n+1)]
# 	print(valueList)
	nextValue=[3,1,2]
	for i,v in enumerate(valueList):
		v3=v%3
		valueList[i]=nextValue[v3]
		nextValue[v3]+=3
	print(" ".join(map(str,valueList)))
		
	

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict


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

colors = [-1] * n

colors[0] = 0

todo = []
for to in edges[0]:
    todo.append([to, 1])

while todo:
    node, color = todo.pop()

    if colors[node] != -1:
        continue

    colors[node] = color
    new_color = 1 - color
    for to in edges[node]:
        if colors[to] != -1:
            continue
        todo.append([to, new_color])

red_count = sum(colors)  # 1
blue_count = n - red_count  # 0

ans = [0] * n

num3s = list(range(3 ,n+1, 3))
nums = [num for num in range(1, n+1) if num % 3 != 0]

if red_count <= n // 3:
    for node in range(n):
        if colors[node] == 1:
            ans[node] = num3s.pop()

        else:
            if num3s:
                num = num3s.pop()
            else:
                num  = nums.pop()
            ans[node] = num


elif blue_count <= n // 3:
    for node in range(n):
        if colors[node] == 0:
            ans[node] = num3s.pop()

        else:
            if num3s:
                num = num3s.pop()
            else:
                num = nums.pop()
            ans[node] = num

else:
    num1s = list(range(1, n+1, 3))
    num2s = list(range(2, n+1, 3))

    for node in range(n):
        if colors[node] == 1:
            if num1s:
                num = num1s.pop()
            else:
                num = num3s.pop()
            ans[node] = num

        else:
            if num2s:
                num = num2s.pop()
            else:
                num = num3s.pop()
            ans[node] = num

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
group = [-1] * N
count = [0] * 2
stack = []
group[0] = 0
count[0] = 1
stack.append(0)
while stack:
    u = stack.pop()
    for v in G[u]:
        if group[v] == -1:
            group[v] = 1 - group[u]
            count[group[v]] += 1
            stack.append(v)
zeros = list(range(3, N+1, 3))
ones = list(range(1, N+1, 3))
twos = list(range(2, N+1, 3))
ans = [0] * N
for g in range(2):
    if count[g] <= N//3:
        for i in range(N):
            if group[i] == 0:
                ans[i] = zeros.pop()
            else:
                if len(twos) > 0:
                    ans[i] = twos.pop()
                elif len(ones) > 0:
                    ans[i] = ones.pop()
                else:
                    ans[i] = zeros.pop()
        print(' '.join(map(str, ans)))
        exit()
print('hi')
for i in range(N):
    if group[i] == 0 and len(ones) > 0:
        ans[i] = ones.pop()
    elif group[i] == 1 and len(twos) > 0:
        ans[i] = twos.pop()
    else:
        ans[i] = zeros.pop()
print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()
inf = 10**9
#ある特定の頂点からの距離がmod３で考えたときに大体同じ数だったら、そのまま振る
#バランスが悪かった場合はうまくやる

#2の時の場合分け
dist = [inf for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dist[i] = dist[node]+1
            dfs(i)
dist[1] = 0
rem_1 = [i+1 for i in range(n) if (i+1) % 3 == 1]
rem_2 = [i+1 for i in range(n) if (i+1) % 3 == 2]
rem_0 = [i+1 for i in range(n) if (i+1) % 3 == 0]
index_0 = 0
index_1 = 1
index_2 = 0
dfs(1)
ans = [1]
for i in range(2,len(dist)):
    if dist[i] % 2 == 1:
        if index_2 < len(rem_2):
            ans.append(rem_2[index_2])
            index_2 += 1
        else:
            ans.append(rem_0[index_0])
            index_0 += 1
    else:
        if index_1 < len(rem_1):
            ans.append(rem_1[index_1])
            index_1 += 1
        else:
            ans.append(rem_0[index_0])
            index_0 += 1
for i in ans:
    print(i, end=" ")

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def dfs(n, d):
    if depth[n] != -1:
        return
    depth[n] = d
    for nn in eAB[n]:
        dfs(nn, d + 1)
    return


N = int(input())
AB = [inpl() for i in range(N - 1)]

eAB = [[] for i in range(N)]
for a, b in AB:
    eAB[a - 1].append(b - 1)
    eAB[b - 1].append(a - 1)

depth = [-1 for i in range(N)]

dfs(0, 0)

eo = [[], []]
for i in range(N):
    eo[depth[i] % 2].append(i)

ans = [-1 for i in range(N)]
if len(eo[0]) > N // 3 and len(eo[1]) > N // 3:
    for i in range(N // 3):
        ans[3 * i] = eo[0][i]
        ans[3 * i + 1] = eo[1][i]
    t_0 = i + 1
    t_1 = i + 1
elif len(eo[0]) <= N // 3:
    for i in range(len(eo[0])):
        ans[3 * i + 2] = eo[0][i]
    t_0 = len(eo[0])
    t_1 = 0
elif len(eo[1]) <= N // 3:
    for i in range(len(eo[1])):
        ans[3 * i + 2] = eo[1][i]
    t_0 = 0
    t_1 = len(eo[1])

for i in range(N):
    if ans[i] != -1:
        continue
    if t_0 < len(eo[0]):
        ans[i] = eo[0][t_0]
        t_0 += 1
    else:
        ans[i] = eo[1][t_1]
        t_1 += 1

print(" ".join(list(map(str, [a + 1 for a in ans]))))

Submission status: Runtime Error

Solution code:
n = int(input())
adjacent_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()
inf = 10**9
#ある特定の頂点からの距離がmod３で考えたときに大体同じ数だったら、そのまま振る
#バランスが悪かった場合はうまくやる

#2の時の場合分け
dist = [inf for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dist[i] = dist[node]+1
            dfs(i)
dist[1] = 0
rem_1 = [i+1 for i in range(n) if (i+1) % 3 == 1]
rem_2 = [i+1 for i in range(n) if (i+1) % 3 == 2]
rem_0 = [i+1 for i in range(n) if (i+1) % 3 == 0]
index_0 = 0
index_1 = 1
index_2 = 0
dfs(1)
ans = [1]
for i in range(2,len(dist)):
    if dist[i] % 2 == 1:
        if index_2 < len(rem_2):
            ans.append(rem_2[index_2])
            index_2 += 1
        else:
            ans.append(rem_0[index_0])
            index_0 += 1
    else:
        if index_1 < len(rem_1):
            ans.append(rem_1[index_1])
            index_1 += 1
        else:
            ans.append(rem_0[index_0])
            index_0 += 1
for i in ans:
    print(i, end=" ")

Submission status: Runtime Error

Solution code:
n = int(input())
adjacent_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()
inf = 10**9
#ある特定の頂点からの距離がmod３で考えたときに大体同じ数だったら、そのまま振る
#バランスが悪かった場合はうまくやる

#2の時の場合分け
dist = [inf for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dist[i] = dist[node]+1
            dfs(i)
dist[1] = 0
rem_1 = [i+1 for i in range(n) if (i+1) % 3 == 1]
rem_2 = [i+1 for i in range(n) if (i+1) % 3 == 2]
rem_0 = [i+1 for i in range(n) if (i+1) % 3 == 0]
index_0 = 0
index_1 = 1
index_2 = 0
dfs(1)
ans = [1]
for i in range(2,len(dist)):
    if dist[i] % 2 == 0:
        if index_2 < len(rem_2):
            ans.append(rem_2[index_2])
            index_2 += 1
        else:
            ans.append(rem_0[index_0])
            index_0 += 1
    else:
        if index_1 < len(rem_1):
            ans.append(rem_1[index_1])
            index_1 += 1
        else:
            ans.append(rem_0[index_0])
            index_0 += 1
for i in ans:
    print(i, end=" ")

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
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)
"""#親のノードに子を入れてくdfs
stack = [1]
parent = [0]*(n+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in g[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)"""
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] ] == c:
            return False
        elif color[ g[v][i] ] == 0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
ans = [0]*(n+1)
t0 = deque([i*3 for i in range(1,n//2)])
t1 = deque([1+i*3 for i in range(0,n//2-1)])
t2 = deque([2+i*3 for i in range(0,n//2-1)])
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:
n = int(input())
adjacent_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()
inf = 10**9
#ある特定の頂点からの距離がmod３で考えたときに大体同じ数だったら、そのまま振る
#バランスが悪かった場合はうまくやる

#2の時の場合分け
dist = [inf for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dist[i] = dist[node]+1
            dfs(i)
dist[1] = 0
rem_1 = [i+1 for i in range(n) if (i+1) % 3 == 1]
rem_2 = [i+1 for i in range(n) if (i+1) % 3 == 2]
rem_0 = [i+1 for i in range(n) if (i+1) % 3 == 0]
index_0 = 0
index_1 = 1
index_2 = 0
ans = [1]
for i in range(2,len(dist)):
    if dist[i] % 2 == 0:
        if index_2 < len(rem_2):
            ans.append(rem_2[index_2])
            index_2 += 1
        else:
            ans.append(rem_0[index_0])
            index_0 += 1
    else:
        if index_1 < len(rem_1):
            ans.append(rem_1[index_1])
            index_1 += 1
        else:
            ans.append(rem_0[index_0])
            index_0 += 1
for i in ans:
    print(i, end=" ")

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
group = [-1] * N
count = [0, 0]
stack = []
group[0] = 0
count[0] = 1
stack.append(0)
while stack:
    u = stack.pop()
    for v in G[u]:
        if group[v] == -1:
            group[v] = 1 - group[u]
            count[group[v]] += 1
            stack.append(v)
zeros = list(range(3, N+1, 3))
ones = list(range(1, N+1, 3))
twos = list(range(2, N+1, 3))
ans = [0] * N
for g in range(2):
    if count[g] <= N//3:
        for i in range(N):
            if group[i] == 0:
                ans[i] = zeros.pop()
            else:
                if len(twos) > 0:
                    ans[i] = twos.pop()
                elif len(ones) > 0:
                    ans[i] = ones.pop()
                else:
                    ans[i] = zeros.pop()
        print(' '.join(map(str, ans)))
        exit()
for i in range(N):
    if group[i] == 0 and len(ones) > 0:
        ans[i] = ones.pop()
    elif group[i] == 1 and len(twos) > 0:
        ans[i] = twos.pop()
    else:
        ans[i] = zeros.pop()
print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

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

print(*dist)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
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)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2

dfs(1)
bl = cl.count(1)
wh = N - bl

nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(nm)

res = [0] * (N + 1)
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
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)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2

dfs(1)
bl = cl.count(1)
wh = N - bl

nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(nm)

res = [0] * (N + 1)
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
group = [-1] * N
count = [0, 0]
stack = []
group[0] = 0
count[0] = 1
stack.append(0)
while stack:
    u = stack.pop()
    for v in G[u]:
        if group[v] != -1:
            group[v] = 1 - group[u]
            count[group[v]] += 1
            stack.append(v)
zeros = list(range(3, N+1, 3))
ones = list(range(1, N+1, 3))
twos = list(range(2, N+1, 3))
ans = [0] * N
for g in range(2):
    if count[g] <= N//3:
        for i in range(N):
            if group[i] == 0:
                ans[i] = zeros.pop()
            else:
                if len(twos) > 0:
                    ans[i] = twos.pop()
                elif len(ones) > 0:
                    ans[i] = ones.pop()
                else:
                    ans[i] = zeros.pop()
        print(' '.join(map(str, ans)))
        exit()
for i in range(N):
    if group[i] == 0 and len(ones) > 0:
        ans[i] = ones.pop()
    elif group[i] == 1 and len(twos) > 0:
        ans[i] = twos.pop()
    else:
        ans[i] = zeros.pop()
print(' '.join(map(str, ans)))

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):
    nex=[]
    for k in x[i]:
        if c[k]==-1:
            c[k]=col
            nex.append(k)
    for k in nex:
        if col==2:
            dfs(k,1)
        else:
            dfs(k,2)

dfs(0,c[0])
d=[]
e=[]
f=[]
lf=n//3
le=n//3+(1 if n%3==2 else 0)
ld=n-lf-le
for i in range(n):
    if c[i]==1:
        if len(d)==ld:
            f.append(i+1)
        else:
            d.append(i+1)
    else:
        x=n//3+(1 if n%3==2 else 0)
        if len(e)==le:
            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)))