Problem:


Score : 600 points

Problem Statement

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

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

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

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

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

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

1\leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

If no permutation satisfies the condition, print -1.

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

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

1 2 5 4 3 

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

p_2 + p_4 = 6

p_2\times p_5 = 6

Thus, this permutation satisfies the condition.



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


Sample output:
1 2 5 4 3

Submission status: Runtime Error

Solution code:
n = int(input())
l = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	l[a-1].append(b-1)
	l[b-1].append(a-1)

distance = [0 for _ in range(n)]
searched = [False for _ in range(n)]
def dfs(k):
	searched[k] = True
	for i in l[k]:
		if searched[i] == False:
			distance[i] = distance[k] + 1
			dfs(i)
	return
dfs(0)
#print(distance)
#print(searched)

cnteven = 0
for i in range(n):
	if distance[i] % 2 == 0:
		cnteven += 1

m = n//3
ans = [0 for _ in range(n)]
cnter1 = 0
cnter2 = 0
cnter3 = 0
ansla = [False for _ in range(n)]
anslb = []
anslc = []
if cnteven <= m:
	#print('cnteven<=', m)
	for i in range(cnteven):
		ansla[3*i+3] = True
	for i in range(n):
		if ansla[i] == False:
			anslb.append(i)
	#print(ansla, anslb)
	for i in range(n):
		if distance[i] % 2 == 0:
			ans[i] = 3 * cnter1 + 3
			cnter1 += 1
		else:
			ans[i] = anslb[cnter2]
			cnter2 += 1
		#print(ans)
elif cnteven >= n-m:
	#print('cnteven>=', n-m)
	for i in range(n-cnteven):
		ansla[3*i+3] = True
	for i in range(n):
		if ansla[i] == False:
			anslb.append(i)
	#print(ansla, anslb)
	for i in range(n):
		if distance[i] % 2 == 1:
			ans[i] = 3 * cnter1 + 3
			cnter1 += 1
		else:
			ans[i] = anslb[cnter2]
			cnter2 += 1
		#print(ans)

else:
	#print('その他')
	for i in range(n):
		#print(distance[i], cnter1, cnter2)
		#print(3*cnter2+2 <= n)
		#print(distance[i] % 2 == 1)
		if (distance[i] % 2 == 0) & (3*cnter1+1 <= n):
			#print(i,'あまり1')
			ans[i] = 3*cnter1+1
			cnter1 += 1
		elif (distance[i] % 2 == 1) & (3*cnter2+2 <= n):
			#print(i,'あまり2')
			ans[i] = 3*cnter2+2
			cnter2 += 1
		else:
			#print(i,'あまり0')
			ans[i] = 3*cnter3+3
			cnter3 += 1
		#print(ans)
answ = ''
for i in range(n-1):
	answ += (str(ans[i]) + ' ')
answ += str(ans[n-1])
print(answ)

Submission status: Runtime Error

Solution code:
# coding: utf-8

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

import numpy as np
a_ = np.arange(1,10000).reshape(-1,1)
b_ = np.arange(2,10001).reshape(-1,1)
ab = np.concatenate([a_, b_], axis=1)
N = 10000

def run(cur, tr, dist, d=1, pre=-1, recur=1, save_recur = []):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        if recur >500:
            dic_ = {'cur':node, 'tr': tr, 'dist': dist,
                              'd': (d + 1) % 2, 'pre': cur, 'recur': recur + 1}
            save_recur.append(dic_)
            return None
        run(node, tr, dist, (d+1)%2, pre=cur, recur=recur+1, save_recur=save_recur)
    return None

if __name__ == '__main__':
    # generate dict
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])

    dist = {0: [1], 1: []}
    save_rec = []
    run(1, tr, dist, save_recur=save_rec)

    while True:
        save_rec2 = save_rec
        save_rec = []
        for dict in save_rec2:
            run(**dict, save_recur = save_rec)
        if save_rec == []:break


    perm = [0] * (N+1)
    rem1_max, rem2_max, rem0_max = int(N/3),int(N/3),int(N/3)
    if N % 3 == 1:
        rem1_max +=1
    if N % 3 == 2:
        rem1_max += 1
        rem2_max += 1
    if (len(dist[0]) <= N/3) | (len(dist[0]) >= 2*N/3):
        bool = int(len(dist[0]) <= N/3)
        h0 = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3*i for i in range(h0, rem0_max+1)] + [3*i+1 for i in range(0, rem1_max)] + [3*i+2 for i in range(0, rem2_max)]
        for k, val in zip(dist[bool], nums):
            perm[k] = val
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        h1 = 0
        h2 = 0
        idx = 0
        bool = int((len(dist[0]) > len(dist[1])))
        for alpha in range(n):
            even = dist[bool][idx]
            perm[even] = alpha * 3 + 1
            odd = dist[1-bool][idx]
            perm[odd] = alpha * 3 + 2
            idx += 1
        h0 = 1
        for k in dist[1-bool][idx:]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3 * i for i in range(h0, rem0_max+1)] + [3 * i + 1 for i in range(n, rem1_max)] + [3 * i + 2 for i in range(n, rem2_max)]

        for h, k in enumerate(dist[bool][idx:]):
            perm[k] = nums[h]
    print(" ".join(list(map(str, perm[1:]))))

Submission status: Runtime Error

Solution code:
# coding: utf-8
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]


def run(cur, tr, dist, d=1, pre=-1):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        run(node, tr, dist, (d+1)%2, pre=cur)
    return None

if __name__ == '__main__':
    # generate dict
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])

    dist = {0: [1], 1: []}
    run(1, tr, dist)

    perm = [0] * (N+1)
    rem1_max, rem2_max, rem0_max = int(N/3),int(N/3),int(N/3)
    if N % 3 == 1:
        rem1_max +=1
    if N % 3 == 2:
        rem1_max += 1
        rem2_max += 1
    if (len(dist[0]) <= N/3) | (len(dist[0]) >= 2*N/3):
        bool = int(len(dist[0]) <= N/3)
        h0 = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3*i for i in range(h0, rem0_max+1)] + [3*i+1 for i in range(0, rem1_max)] + [3*i+2 for i in range(0, rem2_max)]
        for k, val in zip(dist[bool], nums):
            perm[k] = val
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        h1 = 0
        h2 = 0
        idx = 0
        bool = int((len(dist[0]) > len(dist[1])))
        for alpha in range(n):
            even = dist[bool][idx]
            perm[even] = alpha * 3 + 1
            odd = dist[1-bool][idx]
            perm[odd] = alpha * 3 + 2
            idx += 1
        h0 = 1
        for k in dist[1-bool][idx:]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3 * i for i in range(h0, rem0_max+1)] + [3 * i + 1 for i in range(n, rem1_max)] + [3 * i + 2 for i in range(n, rem2_max)]

        for h, k in enumerate(dist[bool][idx:]):
            perm[k] = nums[h]
    print(" ".join(list(map(str, perm[1:]))))

Submission status: Runtime Error

Solution code:
# coding: utf-8
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]


def run(cur, tr, dist, d=1, pre=-1):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        run(node, tr, dist, (d+1)%2, pre=cur)
    return None

if __name__ == '__main__':
    # generate dict
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])

    dist = {0: [1], 1: []}
    run(1, tr, dist)

    perm = [0] * (N+1)
    rem1_max, rem2_max, rem0_max = int(N/3),int(N/3),int(N/3)
    if N % 3 == 1:
        rem1_max +=1
    if N % 3 == 2:
        rem1_max += 1
        rem2_max += 1
    if (len(dist[0]) <= N/3) | (len(dist[0]) >= 2*N/3):
        bool = int(len(dist[0]) <= N/3)
        h0 = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3*i for i in range(h0, rem0_max+1)] + [3*i+1 for i in range(0, rem0_max)] + [3*i+2 for i in range(0, rem2_max)]
        for k, val in zip(dist[bool], nums):
            perm[k] = val
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        h1 = 0
        h2 = 0
        idx = 0
        bool = int((len(dist[0]) > len(dist[1])))
        for alpha in range(n):
            even = dist[bool][idx]
            perm[even] = alpha * 3 + 1
            odd = dist[1-bool][idx]
            perm[odd] = alpha * 3 + 2
            idx += 1
        h0 = 1
        for k in dist[1-bool][idx:]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3 * i for i in range(h0, rem0_max+1)] + [3 * i + 1 for i in range(n, rem1_max)] + [3 * i + 2 for i in range(n, rem2_max)]

        for h, k in enumerate(dist[bool][idx:]):
            perm[k] = nums[h]
    print(" ".join(list(map(str, perm[1:]))))

Submission status: Runtime Error

Solution code:
# coding: utf-8
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

def run(cur, tr, dist, d=1, pre=-1):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        run(node, tr, dist, (d+1)%2, pre=cur)
    return None

if __name__ == '__main__':
    a = [1,2,3,4,5]
    # generate dict
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])
    dist = {0: [1], 1: []}
    run(1, tr, dist)

    perm = [0] * (N+1)
    rem1_max, rem2_max, rem0_max = int(N/3),int(N/3),int(N/3)
    if N % 3 == 1:
        rem1_max +=1
    if N % 3 == 2:
        rem1_max += 1
        rem2_max += 1
    if (len(dist[0]) <= N/3) | (len(dist[0]) >= 2*N/3):
        bool = int(len(dist[0]) < N/3)
        h0 = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3*i for i in range(h0, rem0_max+1)] + [3*i+1 for i in range(0, rem0_max)] + [3*i+2 for i in range(0, rem2_max)]
        for k, val in zip(dist[bool], nums):
            perm[k] = val
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        h1 = 0
        h2 = 0
        idx = 0
        for alpha in range(n):
            even = dist[0][idx]
            perm[even] = alpha * 3 + 1
            odd = dist[1][idx]
            perm[odd] = alpha * 3 + 2
            idx += 1
        bool = (len(dist[0]) > len(dist[1]))
        h0 = 1
        for k in dist[1-bool][idx:]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3 * i for i in range(h0, rem0_max+1)] + [3 * i + 1 for i in range(n, rem1_max)] + [3 * i + 2 for i in range(n, rem2_max)]
        for h, k in enumerate(dist[bool][idx:]):
            perm[k] = nums[h]
    print(" ".join(list(map(str, perm[1:]))))

Submission status: Runtime Error

Solution code:
# coding: utf-8
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

def run(cur, tr, dist, d=1, pre=-1):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        run(node, tr, dist, (d+1)%2, pre=cur)
    return None

if __name__ == '__main__':
    a = [1,2,3,4,5]
    # generate dict
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])
    dist = {0: [1], 1: []}
    run(1, tr, dist)

    perm = [0] * (N+1)
    rem1_max, rem2_max, rem0_max = int(N/3),int(N/3),int(N/3)
    if N % 3 == 1:
        rem1_max +=1
    if N % 3 == 2:
        rem1_max += 1
        rem2_max += 1
    if (len(dist[0]) < N/3) | (len(dist[0]) > 2*N/3):
        bool = int(len(dist[0]) < N/3)
        h0 = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3*i for i in range(h0, rem0_max+1)] + [3*i+1 for i in range(0, rem0_max)] + [3*i+2 for i in range(0, rem2_max)]
        for k, val in zip(dist[bool], nums):
            perm[k] = val
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        h1 = 0
        h2 = 0
        idx = 0
        for alpha in range(n):
            even = dist[0][idx]
            perm[even] = alpha * 3 + 1
            odd = dist[1][idx]
            perm[odd] = alpha * 3 + 2
            idx += 1
        bool = (len(dist[0]) > len(dist[1]))
        h0 = 1
        for k in dist[1-bool][idx:]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3 * i for i in range(h0, rem0_max+1)] + [3 * i + 1 for i in range(n, rem1_max)] + [3 * i + 2 for i in range(n, rem2_max)]
        for h, k in enumerate(dist[bool][idx:]):
            perm[k] = nums[h]
    print(" ".join(list(map(str, perm[1:]))))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

def run(cur, tr, dist, d=1, pre=-1):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        run(node, tr, dist, (d+1)%2, pre=cur)
    return None

if __name__ == '__main__':
    # generate dict
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])

    dist = {0: [1], 1: []}
    run(1, tr, dist)

    perm = [0] * (N+1)
    nums = list(range(N+1))
    if (len(dist[0]) < N/3) | (len(dist[0]) > 2*N/3):
        bool = int(len(dist[0]) < N/3)
        h = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h
            h += 1
            nums.remove(3*h)
        h = 1
        for k in dist[bool]:
            perm[k] = nums[h]
            h += 1
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        for alpha in range(n):
            even = dist[0][0]
            dist[0].remove(even)
            perm[even] = alpha * 3 + 1
            nums.remove(alpha * 3 + 1)
            odd = dist[1][0]
            dist[1].remove(odd)
            perm[odd] = alpha * 3 + 2
            nums.remove(alpha * 3 + 2)
        bool = (len(dist[0]) > len(dist[1]))
        h = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h
            nums.remove(3 * h)
            h += 1
        h=1
        for k in dist[bool]:
            perm[k] = nums[h]
            h += 1
    print(" ".join(list(map(str, perm[1:]))))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

def run(cur, tr, dist, d=1, pre=-1):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        run(node, tr, dist, (d+1)%2, pre=cur)
    return None

if __name__ == '__main__':
    # generate dict
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])

    dist = {0: [1], 1: []}
    run(1, tr, dist)

    perm = [0] * (N+1)
    nums = list(range(N+1))
    if (len(dist[0]) < N/3) | (len(dist[0]) > 2*N/3):
        bool = int(len(dist[0]) < N/3)
        h = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h
            h += 1
            nums.remove(3*h)
        h = 1
        for k in dist[bool]:
            perm[k] = nums[h]
            h += 1
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        for alpha in range(n):
            even = dist[0][0]
            dist[0].remove(even)
            perm[even] = alpha * 3 + 1
            nums.remove(alpha * 3 + 1)
            odd = dist[1][0]
            dist[1].remove(odd)
            perm[odd] = alpha * 3 + 2
            nums.remove(alpha * 3 + 2)
        bool = (len(dist[0]) > len(dist[1]))
        h = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h
            h += 1
            nums.remove(3 * h)
        h=1
        for k in dist[bool]:
            perm[k] = nums[h]
            h += 1
    print(" ".join(list(map(str, perm[1:]))))

Submission status: Runtime Error

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

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if z >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Submission status: Runtime Error

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

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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if z >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <cmath>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if(pow((a + b - c), 2) < 4 * a * b){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Submission status: Runtime Error

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


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))


# あまり１、あまり２、あまり０になるように並び替え
X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]


ans = []
x12, x3 = X[0] + X[1], X[2]
if colors.count(0) <= N // 3:
    for color in colors:
        if color == 0:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

elif colors.count(1) <= N // 3:
    for color in colors:
        if color == 1:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

else:
    for color in colors:
        if X[color]:
            ans.append(X[color ^ 1].pop())
        else:
            ans.append(X[2].pop())

print(' '.join(map(str, ans)))

Submission status: Runtime Error

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


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))


# あまり１、あまり２、あまり０になるように並び替え
X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]


# 少ない色の方は優先的に３の倍数を使うようにして塗る
ans = []
for color in colors:
    if X[color ^ 1]:
        ans.append(X[color ^ 1].pop())
    else:
        ans.append(X[2].pop())

print(' '.join(map(str, ans)))

Submission status: Runtime Error

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


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))


# あまり１、あまり２、あまり０になるように並び替え
X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]


ans = []
for color in colors:
    if X[color]:
        ans.append(X[color].pop())
    else:
        ans.append(X[2].pop())

print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
n = int(input())
G = [[] for i in range(n)]

#for文の変数に_を使うことの意味は、そのfor文の中で変数を使っていないことを表す
for _ in range(n-1):
    a,b = map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    #print(G)
    G[b].append(a)
    #print(G)
    #print('=============')
#*の演算子を使うことで、任意の要素数を持つリストを0で初期化できる
group  = [-1] * n
#group [-1, -1, -1, -1, -1]
group[0] = False

def categorize2g(pi, i, g):
    for ci in G[i]:
        if ci == pi:
            #continueは次のループへスキップ
            continue
        group[ci] = not g
        #print(group)
        #print('=======')
        categorize2g(i, ci, not g)

categorize2g(-1,1,0)

ans = [0]*n

mod0 = [x for x in range(1, n+1) if x%3 == 0]
mod1 = [x for x in range(1, n+1) if x%3 == 1]
mod2 = [x for x in range(1, n+1) if x%3 == 2]
#TrueとFalseはそれぞれ1と0なのでsumを使うことでTrueの数を調べることができる
gtnum = sum(group)

from collections import deque
if gtnum <= n/3:
    dq = deque(mod1+mod2+mod0)
elif n-gtnum <= n/3:
    dq = deque(mod0+mod1+mod2)
else:
    dq = deque(mod1+mod0+mod2)


if len(ans) == n:
    #enumerateは要素番号と要素を取り出す
    for i, g in enumerate(group):
        if g:
            #popは末尾（右側）を削除し、その値を取り出す。
            ans[i] = dq.pop()
        else:
            #popleftは先頭（左側）を削除し、その値を取り出す
            ans[i] = dq.popleft()


#mapでansのそれぞれの要素をstr型に変換して、joinで半角スペースごとそれぞれくっつける
print(" ".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
n = int(input())
G = [[] for i in range(n)]

#for文の変数に_を使うことの意味は、そのfor文の中で変数を使っていないことを表す
for _ in range(n-1):
    a,b = map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    #print(G)
    G[b].append(a)
    #print(G)
    #print('=============')
#*の演算子を使うことで、任意の要素数を持つリストを0で初期化できる
group  = [-1] * n
#group [-1, -1, -1, -1, -1]
group[0] = False

def categorize2g(pi, i, g):
    for ci in G[i]:
        if ci == pi:
            #continueは次のループへスキップ
            continue
        group[ci] = not g
        #print(group)
        #print('=======')
        categorize2g(i, ci, not g)

categorize2g(-1,0,0)

ans = [0]*n

mod0 = [x for x in range(1, n+1) if x%3 == 0]
mod1 = [x for x in range(1, n+1) if x%3 == 1]
mod2 = [x for x in range(1, n+1) if x%3 == 2]
#TrueとFalseはそれぞれ1と0なのでsumを使うことでTrueの数を調べることができる
gtnum = sum(group)

from collections import deque
if gtnum <= n//3:
    dq = deque(mod1+mod2+mod0)
elif n-gtnum <= n//3:
    dq = deque(mod0+mod1+mod2)
else:
    dq = deque(mod1+mod0+mod2)


if len(ans) == n:
    #enumerateは要素番号と要素を取り出す
    for i, g in enumerate(group):
        if g:
            #popは末尾（右側）を削除し、その値を取り出す。
            ans[i] = dq.pop()
        else:
            #popleftは先頭（左側）を削除し、その値を取り出す
            ans[i] = dq.popleft()


#mapでansのそれぞれの要素をstr型に変換して、joinで半角スペースごとそれぞれくっつける
print(" ".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
n = int(input())
G = [[] for i in range(n)]

#for文の変数に_を使うことの意味は、そのfor文の中で変数を使っていないことを表す
for _ in range(n-1):
    a,b = map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    #print(G)
    G[b].append(a)
    #print(G)
    #print('=============')
#*の演算子を使うことで、任意の要素数を持つリストを0で初期化できる
group  = [-1] * n
#group [-1, -1, -1, -1, -1]
group[0] = False

def categorize2g(pi, i, g):
    for ci in G[i]:
        if ci == pi:
            #continueは次のループへスキップ
            continue
        group[ci] = not g
        #print(group)
        #print('=======')
        categorize2g(i, ci, not g)

categorize2g(-1,1,0)

ans = [0]*n

mod0 = [x for x in range(1, n+1) if x%3 == 0]
mod1 = [x for x in range(1, n+1) if x%3 == 1]
mod2 = [x for x in range(1, n+1) if x%3 == 2]
#TrueとFalseはそれぞれ1と0なのでsumを使うことでTrueの数を調べることができる
gtnum = sum(group)

from collections import deque
if gtnum <= n//3:
    dq = deque(mod1+mod2+mod0)
elif n-gtnum <= n//3:
    dq = deque(mod0+mod1+mod2)
else:
    dq = deque(mod1+mod0+mod2)


if len(ans) == n:
    #enumerateは要素番号と要素を取り出す
    for i, g in enumerate(group):
        if g:
            #popは末尾（右側）を削除し、その値を取り出す。
            ans[i] = dq.pop()
        else:
            #popleftは先頭（左側）を削除し、その値を取り出す
            ans[i] = dq.popleft()


#mapでansのそれぞれの要素をstr型に変換して、joinで半角スペースごとそれぞれくっつける
print(" ".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

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

# process
def f(i):
    if tg[i] == 0 and mod3[1] <= N:
        ans[i] = mod3[1]
        mod3[1] += 3
    elif tg[i] == 1 and mod3[2] <= N:
        ans[i] = mod3[2]
        mod3[2] += 3
    elif mod3[0] <= N:
        ans[i] = mod3[0]
        mod3[0] += 3
    else:
        ans.clear()

    g = (tg[i]+1)%2
    for p in Tree[i]:
        if p == i or tg[p] != -1:
            continue
        
        tg[p] = g
        if not f(p):
            return False
    
    return True

tg = [-1]*N
tg[0] = 0
ans = [0]*N
mod3 = [3, 1, 2]

f(0)

# output
# print(tg)

if len(ans) == 0:
    if tg.count(0) < 2 or N - tg.count(0) < 2:
        ans = [0]*N
        for i in range(0, N):
            ans[i] = i+1
    else:
        ans = [-1]

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

Submission status: Runtime Error

Solution code:
import sys
 
sys.setrecursionlimit(10 ** 6)
n = int(input())
 
edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even =[]
nums = [[],[],[]]
for i in range(1,n+1):
    nums[i % 3].append(i)
 
def dfs(x, last = -1, d = 0):
    if d % 2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:continue
        dfs(nxt, x, d + 1)
 
for i in range(n-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
 
dfs(0)
 
# zerocnt = len(nums[0])
 
# if len(even) <= zerocnt:
#     for even_node in even:
#         ans[even_node] = nums[0].pop()
#     rest = nums[0] + nums[1] + nums[2]
#     for odd_node in odd:
#         ans[odd_node] = rest.pop()
 
# elif len(odd) <= zerocnt:
#     for odd_node in odd:
#         ans[odd_node] = nums[0].pop()
#     rest = nums[0] + nums[1] + nums[2]
#     for even_node in even:
#         ans[even_node] = rest.pop()
 

# else:
for num in nums[1]:
    ans[even.pop()] = num
for num in nums[2]:
    ans[odd.pop()] = num
rest = nums[0]
for even_node in even:
    ans[even_node] = rest.pop()
for odd_node in odd:
    ans[odd_node] = rest.pop()
 
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
 
sys.setrecursionlimit(10 ** 6)
n = int(input())
 
edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even =[]
nums = [[],[],[]]
for i in range(1,n+1):
    nums[i % 3].append(i)
 
def dfs(x, last = -1, d = 0):
    if d % 2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:continue
        dfs(nxt, x, d + 1)
 
for i in range(n-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
 
dfs(0)
 
zerocnt = len(nums[0])
 
# if len(even) <= zerocnt:
#     for even_node in even:
#         ans[even_node] = nums[0].pop()
#     rest = nums[0] + nums[1] + nums[2]
#     for odd_node in odd:
#         ans[odd_node] = rest.pop()
 
# elif len(odd) <= zerocnt:
#     for odd_node in odd:
#         ans[odd_node] = nums[0].pop()
#     rest = nums[0] + nums[1] + nums[2]
#     for even_node in even:
#         ans[even_node] = rest.pop()
 
# len
# nums[1] >= nums[2] >= nums[0] >= nums[1]-1
# else:
    for num in nums[1]:
        ans[even.pop()] = num
    for num in nums[2]:
        ans[odd.pop()] = num
    rest = nums[0]
    for even_node in even:
        ans[even_node] = rest.pop()
    for odd_node in odd:
        ans[odd_node] = rest.pop()
 
print(*ans)