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

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(nodes, src):
    """ DFS(木、スタック、重みなし) """

    N = len(nodes)
    stack = [(src, -1, 0)]
    dist = [-1] * N
    while stack:
        u, prev, c = stack.pop()
        dist[u] = c
        for v in nodes[u]:
            if v != prev:
                # 0,1を交互に入れて二部グラフを塗り分け
                stack.append((v, u, 1-c))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for _ in range(N-1):
    a, b = MAP()
    a -= 1; b-= 1
    nodes[a].append(b)
    nodes[b].append(a)

res = dfs(nodes, 0)
cnt0 = res.count(0)
cnt1 = res.count(1)

ans = [0] * N
# グラフの偏りによって場合分け
if cnt0 <= N // 3 or cnt1 <= N // 3:
    if cnt0 > cnt1:
        cnt0, cnt1 = cnt1, cnt0
        res = [1-c for c in res]
    # 少ない方全部に0mod3入れて、多い方は残りを適当に入れる
    p1 = 1
    p2 = 2
    p3 = 3
    for i in range(N):
        if res[i] == 0:
            ans[i] = p3
            p3 += 3
        else:
            if p1 <= N:
                ans[i] = p1
                p1 += 3
            elif p2 <= N:
                ans[i] = p2
                p2 += 3
            else:
                ans[i] = p3
                p3 += 3

else:
    # それぞれに1mod3と2mod3を優先して入れて、なくなったら残りには0mod3を入れる
    p1 = 1
    p2 = 2
    p3 = 3
    for i in range(N):
        if res[i] == 0:
            if p1 <= N:
                ans[i] = p1
                p1 += 3
            else:
                ans[i] = p3
                p3 += 3
        else:
            if p2 <= N:
                ans[i] = p2
                p2 += 3
            else:
                ans[i] = p3
                p3 += 3
print(*ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)

def main():
    n=int(input())
    tree=[[] for i in range(n)]
    for _ in range(n-1):
       a,b=map(int,input().split())
       a-=1
       b-=1
       tree[a].append(b)
       tree[b].append(a)
    
    depth=[-1]*n
    depth[0]=0

    def dfs(i):
        for e in tree[i]:
            if depth[e]==-1:
                depth[e]=(depth[i]+1)%2
                dfs(e)
    dfs(0)
    o=sum(depth)
    e=n-o

    if n%3==0:
        i = n//3
        j = i
        k = i
    elif n%3==1:
        i = n//3
        j = i+1
        k = i
    else:
        i = n//3
        j = i+1
        k = j

    ans=[0]*n
    if 3*e > n and 3*o > n:
        for l in range(n):
            if depth[l]==0:
                if j==0:
                    ans[l]=3*i
                    i-=1
                else:
                    ans[l]=3*j-2
                    j-=1
            else:
                if k==0:
                    ans[l]=3*i
                    i-=1
                else:
                    ans[l]=3*k-1
                    k-=1
    
    elif 3*e <= n:
        for l in range(n):
            if depth[l]==0:
                ans[l]=3*i
                i-=1
            else:
                if j==0 and k==0:
                    ans[l]=3*i
                    i-=1
                elif j==0:
                    ans[l]=3*k-1
                    k-=1
                else:
                    ans[l]=3*j-2
                    j-=1
    
    else:
        for l in range(n):
            if depth[l]==1:
                ans[l]=3*i
                i-=1
            else:
                if j==0 and k==0:
                    ans[l]=3*i
                    i-=1
                elif j==0:
                    ans[l]=3*k-1
                    k-=1
                else:
                    ans[l]=3*j-2
                    j-=1
    print(*ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dfs(nodes, src):
    """ DFS(木、スタック、重みなし) """

    N = len(nodes)
    stack = [(src, -1, 0)]
    dist = [-1] * N
    while stack:
        u, prev, c = stack.pop()
        dist[u] = c
        for v in nodes[u]:
            if v != prev:
                # 0,1を交互に入れて二部グラフを塗り分け
                stack.append((v, u, 1-c))
    return dist

N = INT()
nodes = [[] for i in range(N)]
for _ in range(N-1):
    a, b = MAP()
    a -= 1; b-= 1
    nodes[a].append(b)
    nodes[b].append(a)

res = dfs(nodes, 0)
cnt0 = res.count(0)
cnt1 = res.count(1)

ans = [0] * N
# グラフの偏りによって場合分け
if cnt0 <= N // 3 or cnt1 <= N // 3:
    if cnt0 > cnt1:
        cnt0, cnt1 = cnt1, cnt0
        res = [1-c for c in res]
    # 少ない方に全部0mod3入れて、多い方は残りを適当に入れる
    p12 = 1
    p3 = 3
    for i in range(N):
        if res[i] == 0:
            ans[i] = p3
            p3 += 3
    for i in range(N):
        if res[i] == 1:
            if p12 <= N:
                ans[i] = p12
                p12 += 1
                if p12 % 3 == 0:
                    p12 += 1
            else:
                ans[i] = p3
                p3 += 3

else:
    # それぞれに1mod3と2mod3を優先して入れて、なくなったら残りには0mod3を入れる
    p1 = 1
    p2 = 2
    p3 = 3
    for i in range(N):
        if res[i] == 0:
            if p1 <= N:
                ans[i] = p1
                p1 += 3
            else:
                ans[i] = p3
                p3 += 3
        else:
            if p2 <= N:
                ans[i] = p2
                p2 += 3
            else:
                ans[i] = p3
                p3 += 3
print(*ans)

Submission status: Accepted

Solution code:
#####
 
import numpy as np
from numpy import int32, int8
from collections import defaultdict

#####
 
def getIntList(inp):
	return [int(_) for _ in inp]
 
 
from sys import stdin
import sys
sys.setrecursionlimit(10**6) 
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)
	
# 	for v0 in sorted(edge): print(v0, sorted(edge[v0]))
	
	depths=np.empty(n, np.bool)
	dfs(1, depths, 0, edge, -1)
# 	for i in range(n):print(i+1,depths[i])
# 	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, int32)
	sum0=(depths==0).sum()
	sum1=(depths==1).sum()
	
# 	global counts
	
	if sum0<=remainingMod[0]:
# 		counts[0]+=1
		values[depths==0]=0
		remainingMod[0]-=sum0
		remaining=np.concatenate([v*np.ones(remainingMod[v], int32) for v in range(3)])
		values[depths==1]=remaining
	
	elif sum1<=remainingMod[0]:
# 		counts[1]+=1
		values[depths==1]=0
		remainingMod[0]-=sum1
		remaining=np.concatenate([v*np.ones(remainingMod[v], int32) for v in range(3)])
		values[depths==0]=remaining
		
	else:
# 		counts[2]+=1
		remaining=np.concatenate([1*np.ones(remainingMod[1], int32), np.zeros(sum0-remainingMod[1])])
		values[depths==0]=remaining
		remaining=np.concatenate([2*np.ones(remainingMod[2], int32), np.zeros(sum1-remainingMod[2])])
		values[depths==1]=remaining
	
	values[values==0]=np.arange((values==0).sum())*3+3
	values[values==1]=np.arange((values==1).sum())*3+1
	values[values==2]=np.arange((values==2).sum())*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
# 	
# # 	for v0 in sorted(v3):
# # 		print(v0, sorted(v3[v0]))
# 	
# # 	print("testing")
# 	ok=True
# 	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:
# 				pass
# # 				print(v0, val0%3, v1, val1%3, "ok")
# 			else:
# # 				print(v0, val0%3, v1, val1%3, "NG")
# 				ok=False
# 	assert ok
 
 
if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Accepted

Solution code:
n = int(input())
lst = [[] for i in range(n+1)]
for i in range(n-1):
    ai, bi = map(int, input().split())
    lst[ai].append(bi)
    lst[bi].append(ai)

tf = [0 for i in range(n+1)]
tf[1] = 1
iro = 1
queue = lst[1]
while queue != []:
    iro = -iro
    new_queue = []
    for i in queue:
        tf[i] = iro
        for j in lst[i]:
            if tf[j] == 0:
                new_queue.append(j)
    queue = new_queue

n_minus = tf.count(-1)
n_plus = tf.count(1)
ans = [0 for i in range(n)]

if n_minus <= n//3:
    bai = 1
    for i in range(1, n+1):
        if tf[i] == -1:
            ans[i-1] = 3 * bai
            bai += 1
    kouho = 1
    for i in range(1, n+1):
        if tf[i] == 1:
            if bai <= n//3:
                ans[i-1] = 3 * bai
                bai += 1
            else:
                ans[i-1] = kouho
                kouho += 1
                if kouho % 3 == 0:
                    kouho += 1

elif n_plus <= n//3:
    bai = 1
    for i in range(1, n+1):
        if tf[i] == 1:
            ans[i-1] = 3 * bai
            bai += 1
    kouho = 1
    for i in range(1, n+1):
        if tf[i] == -1:
            if bai <= n//3:
                ans[i-1] = 3 * bai
                bai += 1
            else:
                ans[i-1] = kouho
                kouho += 1
                if kouho % 3 == 0:
                    kouho += 1

else:
    bai = 1
    kouho1 = 1
    kouho2 = 2
    for i in range(1, n+1):
        if tf[i] == 1:
            if kouho1 <= n:
                ans[i-1] = kouho1
                kouho1 += 3
            else:
                ans[i-1] = 3 * bai
                bai += 1
        else:
            if kouho2 <= n:
                ans[i-1] = kouho2
                kouho2 += 3
            else:
                ans[i-1] = 3 * bai
                bai += 1

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

Submission status: Accepted

Solution code:
n = int(input())
lst = [[] for i in range(n+1)]
for i in range(n-1):
    ai, bi = map(int, input().split())
    lst[ai].append(bi)
    lst[bi].append(ai)

tf = [0 for i in range(n+1)]
tf[1] = 1
iro = 1
queue = lst[1]
while queue != []:
    iro = -iro
    new_queue = []
    for i in queue:
        if tf[i] == 0:
            tf[i] = iro
            for j in lst[i]:
                if tf[j] == 0:
                    new_queue.append(j)
    queue = new_queue

n_minus = tf.count(-1)
n_plus = tf.count(1)
ans = [0 for i in range(n)]

if n_minus <= n//3:
    bai = 1
    for i in range(1, n+1):
        if tf[i] == -1:
            ans[i-1] = 3 * bai
            bai += 1
    kouho = 1
    for i in range(1, n+1):
        if tf[i] == 1:
            if bai <= n//3:
                ans[i-1] = 3 * bai
                bai += 1
            else:
                ans[i-1] = kouho
                kouho += 1
                if kouho % 3 == 0:
                    kouho += 1

elif n_plus <= n//3:
    bai = 1
    for i in range(1, n+1):
        if tf[i] == 1:
            ans[i-1] = 3 * bai
            bai += 1
    kouho = 1
    for i in range(1, n+1):
        if tf[i] == -1:
            if bai <= n//3:
                ans[i-1] = 3 * bai
                bai += 1
            else:
                ans[i-1] = kouho
                kouho += 1
                if kouho % 3 == 0:
                    kouho += 1

else:
    bai = 1
    kouho1 = 1
    kouho2 = 2
    for i in range(1, n+1):
        if tf[i] == 1:
            if kouho1 <= n:
                ans[i-1] = kouho1
                kouho1 += 3
            else:
                ans[i-1] = 3 * bai
                bai += 1
        else:
            if kouho2 <= n:
                ans[i-1] = kouho2
                kouho2 += 3
            else:
                ans[i-1] = 3 * bai
                bai += 1

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

Submission status: Accepted

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

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

color = [-1] * n  # 木は二分グラフなので彩色

queue = deque([0])
color[0] = 0
red_blue = [1, 0]  # 色毎に塗った数を記録

while queue:
    now = queue.popleft()
    for to in G[now]:
        if color[to] == -1:
            color[to] = 1 - color[now]
            red_blue[color[to]] += 1
            queue.append(to)

ans = [-1] * n  # 異なる色が塗られたもの同士の数字がmod3で同じにならなければ十分
if 3*red_blue[0] < n:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 0:
            ans[i] = 3 * three + 3
            three += 1
        else:
            if 3*one + 1 <= n:
                ans[i] = 3 * one + 1
                one += 1
            elif 3*two+2 <= n:
                ans[i] = 3 * two + 2
                two += 1
            else:
                ans[i] = 3 * three + 3
                three += 1
elif 3*red_blue[1] < n:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 1:
            ans[i] = 3 * three + 3
            three += 1
        else:
            if 3 * one + 1 <= n:
                ans[i] = 3 * one + 1
                one += 1
            elif 3 * two + 2 <= n:
                ans[i] = 3 * two + 2
                two += 1
            else:
                ans[i] = 3 * three + 3
                three += 1
else:
    one, two, three = 0, 0, 0
    for i in range(n):
        if color[i] == 0:
            if 3*one+1 <= n:
                ans[i] = 3*one+1
                one += 1
            else:
                ans[i] = 3*three+3
                three += 1
        else:
            if 3*two+2 <= n:
                ans[i] = 3*two+2
                two += 1
            else:
                ans[i] = 3*three+3
                three += 1
                
print(*ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
# AB = generate_tree(N)


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

bp = [-1] * N
stack = [(0, None, 0)]
while stack:
    v, p, b = stack.pop()
    bp[v] = b
    b += 1
    b &= 1
    for u in graph[v]:
        if u == p:
            continue
        stack.append((u, v, b))

cnt0 = N // 3
cnt1 = (N + 2) // 3
cnt2 = (N + 1) // 3
vs0 = [i for i, b in enumerate(bp) if b == 0]
vs1 = [i for i, b in enumerate(bp) if b == 1]
ans_mod3 = [-1] * N
if bp.count(0) <= N // 3:
    for i in range(len(vs0)):
        ans_mod3[vs0.pop()] = 0
        cnt0 -= 1
elif bp.count(1) <= N // 3:
    for i in range(len(vs1)):
        ans_mod3[vs1.pop()] = 0
        cnt0 -= 1
else:
    for i in range(cnt1):
        ans_mod3[vs0.pop()] = 1
        cnt1 -= 1
    for i in range(cnt2):
        ans_mod3[vs1.pop()] = 2
        cnt2 -= 1

for _ in range(cnt0):
    if vs0:
        ans_mod3[vs0.pop()] = 0
    elif vs1:
        ans_mod3[vs1.pop()] = 0
for _ in range(cnt1):
    if vs0:
        ans_mod3[vs0.pop()] = 1
    elif vs1:
        ans_mod3[vs1.pop()] = 1
for _ in range(cnt2):
    if vs0:
        ans_mod3[vs0.pop()] = 2
    elif vs1:
        ans_mod3[vs1.pop()] = 2

st = [3, 1, 2]
ans = []
for a in ans_mod3:
    ans.append(st[a])
    st[a] += 3
print(*ans)

Submission status: Accepted

Solution code:
# 完全二部グラフで大丈夫なら全部大丈夫(最悪で大丈夫かどうか)
# 簡単のためN=3kとする(3の倍数以外でもほとんど同じなので)
# 0,1,2がk個ずつ

# 1-1,2-2間に辺があるとダメ(これだけを避ければよい)
#   1-2,1-0,2-1,2-0,0-0はOKなので

# 二部グラフで片側の頂点が2k以上(もう一方がk個以下)の場合
#   2k以上の方に1,2を割り当てて、反対側をすべて0にする

# 両方とも(k,2k)の場合
# 両方k以上なのでLを1、Rを2で埋めて残りを0で埋める


def main():
    from collections import deque
    from itertools import chain
    import sys
    input = sys.stdin.readline

    # INPUT
    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    # BFS
    dq = deque([0])
    parity = [-1] * N
    parity[0] = 0
    size_0 = 0
    while dq:
        v = dq.popleft()
        p = parity[v]
        if p == 0:
            size_0 += 1
        np = 1 ^ p
        for u in graph[v]:
            if ~parity[u]: continue
            parity[u] = np
            dq.append(u)

    # SOLVE
    k = N // 3  # 3の倍数の個数
    g1 = iter(range(1, N + 1, 3))  # rangeのままだとchain(g1,g2,g3)としたときg3が途中から始まらない
    g2 = iter(range(2, N + 1, 3))  # range != iteratorなので消費が共有されないため
    g3 = iter(range(3, N + 1, 3))
    if size_0 <= k:  # parity=0を3の倍数で埋め,残りを余った数で埋める
        g123 = chain(g1, g2, g3)
        ret = (next(g3) if p == 0 else next(g123) for p in parity)

    elif N - size_0 <= k:  # parity=1を3の倍数で埋め,残りを余った数で埋める
        g123 = chain(g1, g2, g3)
        ret = (next(g3) if p == 1 else next(g123) for p in parity)

    else:  # parity=0を(mod3=1)で,parity=1を(mod3=2)で埋め,残りを3の倍数で埋める
        g13 = chain(g1, g3)
        g23 = chain(g2, g3)
        ret = (next(g13) if p == 0 else next(g23) for p in parity)

    print(*ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 完全二部グラフで大丈夫なら全部大丈夫(最悪で大丈夫かどうか)
# 簡単のためN=3kとする(3の倍数以外でもほとんど同じなので)
# 0,1,2がk個ずつ

# 1-1,2-2間に辺があるとダメ(これだけを避ければよい)
#   1-2,1-0,2-1,2-0,0-0はOKなので

# 二部グラフで片側の頂点が2k以上(もう一方がk個以下)の場合
#   2k以上の方に1,2を割り当てて、反対側をすべて0にする

# 両方とも(k,2k)の場合
# 両方k以上なのでLを1、Rを2で埋めて残りを0で埋める


def main():
    from collections import deque
    from itertools import chain
    import sys
    input = sys.stdin.readline

    # INPUT
    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    # BFS
    dq = deque([0])
    parity = [-1] * N
    parity[0] = 0

    vs = [[] for _ in range(2)]
    vs[0].append(0)

    while dq:
        v = dq.popleft()
        p = parity[v]
        np = 1 ^ p
        for u in graph[v]:
            if ~parity[u]: continue
            parity[u] = np
            vs[np].append(u)
            dq.append(u)

    # SOLVE
    k = N // 3  # 3の倍数の個数

    g1 = iter(range(1, N + 1, 3))
    g2 = iter(range(2, N + 1, 3))
    g3 = iter(range(3, N + 1, 3))
    if len(vs[0]) <= k:
        # parity=0を3の倍数で埋める
        # 残りを余った数で埋める
        for v in vs[0]:
            parity[v] = next(g3)  # g3の方がvs[0]より数多い

        g123 = chain(g1, g2, g3)

        for v in vs[1]:
            parity[v] = next(g123)

    elif len(vs[1]) <= k:
        # parity=1を3の倍数で埋める
        # 残りを余った数で埋める
        for v in vs[1]:
            parity[v] = next(g3)  # g3の方がvs[1]より数多い

        g123 = chain(g1, g2, g3)

        for v in vs[0]:
            parity[v] = next(g123)

    else:
        # parity=0を(mod3=1)で埋める
        # parity=1を(mod3=2)で埋める
        # 残りを3の倍数で埋める

        g13 = chain(g1, g3)
        for v in vs[0]:
            parity[v] = next(g13)
            # k<=len(g1)<=k+1,len(vs[0])>=k+1
            # 右辺がg1だけだと不足する恐れ

        g23 = chain(g2, g3)
        for v in vs[1]:
            parity[v] = next(g23)
            # k<=len(g2)<=k+1,len(vs[1])>=k+1
            # 右辺がg2だけだと不足する恐れ

    print(*parity)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    ab = [tuple(map(int, input().split())) for _ in range(N - 1)]

    to = [[] for _ in range(N)]
    for a, b in ab:
        to[a - 1].append(b - 1)
        to[b - 1].append(a - 1)

    c1 = list(range(1, N + 1, 3))
    c2 = list(range(2, N + 1, 3))
    c3 = list(range(3, N + 1, 3))

    color = [0] * N

    for root in range(N):
        if len(to[root]) == 1:
            break

    queue = set([root])
    color[root] = 1
    while queue:
        v = queue.pop()
        color_v = color[v]
        for i in to[v]:
            if color[i] == 0:
                color[i] = 3 - color_v
                queue.add(i)

    ans = [0] * N
    order = sorted(range(N), key=lambda x: color[x])
    if color.count(1) <= N / 3:
        for i in order:
            if c3:
                ans[i] = c3.pop(-1)
            elif c1:
                ans[i] = c1.pop(-1)
            else:
                ans[i] = c2.pop(-1)
    elif color.count(2) <= N / 3:
        for i in reversed(order):
            if c3:
                ans[i] = c3.pop(-1)
            elif c1:
                ans[i] = c1.pop(-1)
            else:
                ans[i] = c2.pop(-1)
    else:
        for i in range(N):
            if (color[i] == 1) and c1:
                ans[i] = c1.pop(-1)
            elif (color[i] == 2) and c2:
                ans[i] = c2.pop(-1)
            else:
                ans[i] = c3.pop(-1)

    print(*ans)


main()

Submission status: Accepted

Solution code:
n = int(input())
con = [set() for _ in range(n)]
tree = [0]*n

for _ in range(n-1):
    a,b = map(int,input().split())
    con[a-1].add(b)
    con[b-1].add(a)

checked = set([1])
stack = list(con[0])
stack_ = []
while len(checked) < n:
    while stack:
        x = stack.pop()
        if x in checked:
            continue
        checked.add(x)
        stack_.extend(con[x-1])
        tree[x-1] = 1
        
    while stack_:
        x = stack_.pop()
        if x in checked:
            continue
        checked.add(x)
        stack.extend(con[x-1])

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

ans = [0]*n
sum_tree = sum(tree)
if sum_tree < n/3:
    for i in range(n):
        if tree[i] == 0:
            if mod1:
                ans[i] = mod1.pop()
            elif mod2:
                ans[i] = mod2.pop()
            else:
                ans[i] = mod0.pop()
        else:
            ans[i] = mod0.pop()
elif sum_tree > n*2/3:
    for i in range(n):
        if tree[i] == 1:
            if mod1:
                ans[i] = mod1.pop()
            elif mod2:
                ans[i] = mod2.pop()
            else:
                ans[i] = mod0.pop()
        else:
            ans[i] = mod0.pop() 
else:
    for i in range(n):
        if tree[i] == 0:
            if mod1:
                ans[i] = mod1.pop()
            else:
                ans[i] = mod0.pop()
        else:
            if mod2:
                ans[i] = mod2.pop()
            else:
                ans[i] = mod0.pop()
            
print(" ".join(map(lambda x:str(x), ans)))

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(2147483647)

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


vertice = [-1 for _ in range(n)]
stack = [(0, 0)]

while stack:
    parent, vertex = stack.pop()
    vertice[vertex] = vertice[parent] * (-1)
    for next in edges[vertex]:
        if next != parent:
            stack.append((vertex, next))

# vertice = [0 for _ in range(n)]
#
#
# def dfs(v, color_i):
#     vertice[v] = color_i
#     for i in edges[v]:
#         if vertice[i] == 0:
#             dfs(i, color_i*(-1))
#
# dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(not3.pop()))
        else:
            if not3:
                ans.append(str(not3.pop()))
            else:
                ans.append(str(num3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(not3.pop()))
        else:
            if not3:
                ans.append(str(not3.pop()))
            else:
                ans.append(str(num3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Submission status: Accepted

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 k in range(1, N + 1):
    if k % 3 == 0:
        mod0.append(k)
    elif k % 3 == 1:
        mod1.append(k)
    else:
        mod2.append(k)

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()
            elif mod0:
                node_p[i] = mod0.pop()
            else:
                print(-1)
                exit(0)
        else:
            if mod2:
                node_p[i] = mod2.pop()
            elif mod0:
                node_p[i] = mod0.pop()
            else:
                print(-1)
                exit(0)

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


odd = 0
even = 0

bfs(N)

for i in range (1,N + 1):
    if dist[i] % 2 == 0:
        even += 1
    else:
        odd += 1

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

print()

Submission status: Accepted

Solution code:
from collections import deque
import random
isdebug=0
if isdebug==0:
    N=int(input())
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
else:
    N=20*10**4
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=random.randrange(i+1),i+1
        G[a].append(b)
        G[b].append(a)
dist=[-1 for i in range(N)]
X=[]
Y=[]
q=deque([0])
dist[0]=0
while(len(q)>0):
    r=q.popleft()
    if dist[r]%2==0:
        X.append(r)
    else:
        Y.append(r)
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=dist[r]+1
            q.append(p)
P=[0 for i in range(N)]
que=deque([])
if min(len(X),len(Y))<=N//3:
    for i in range(1,N+1):
        if i%3==0:
            que.appendleft(i)
        else:
            que.append(i)
    if len(X)<len(Y):
        for i in X:
            t=que.popleft()
            P[i]=t
        for i in Y:
            t=que.pop()
            P[i]=t
    else:
        for i in Y:
            t=que.popleft()
            P[i]=t
        for i in X:
            t=que.pop()
            P[i]=t
else:
    for i in range(1,N+1):
        if i%3==0:
            que.appendleft(i)
    for i in range(1,N+1):
        if i%3==1:
            que.appendleft(i)
        elif i%3==2:
            que.append(i)
    for i in X:
        t=que.popleft()
        P[i]=t
    for i in Y:
        t=que.pop()
        P[i]=t
print(*P)