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.

Solution (Python):
from collections import defaultdict, Counter, deque

N, = list(map(int, input().split()))

g = defaultdict(list)
for i in range(N - 1):
    u, v = list(map(int, input().split()))
    g[u].append(v)
    g[v].append(u)


source = 1
dist = {}
q = deque()
q.append(source)
dist[source] = 0
while q:
    node = q.popleft()
    level = dist[node]
    for nbr in g[node]:
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = level + 1

mod1 = list(range(1, N + 1, 3))
mod2 = list(range(2, N + 1, 3))
mod0 = list(range(3, N + 1, 3))


parityCounts = Counter(level % 2 for level in dist.values())

assign = {}

if min(parityCounts[0], parityCounts[1]) <= len(mod0):
    
    parityOfSmaller = min([0, 1], key=lambda k: parityCounts[k])
    for i in range(1, N + 1):
        if dist[i] % 2 == parityOfSmaller:
            assign[i] = mod0.pop()
        else:
            if mod1:
                assign[i] = mod1.pop()
            elif mod2:
                assign[i] = mod2.pop()
            elif mod0:
                assign[i] = mod0.pop()
else:
    
    
    
    
    assert len(mod0) <= len(mod2) <= len(mod1)

    if parityCounts[0] < parityCounts[1]:
        assert len(mod2) <= parityCounts[0]
        assert len(mod1) <= parityCounts[1]
        parityToMod = {0: mod2, 1: mod1}
    else:
        assert len(mod1) <= parityCounts[0]
        assert len(mod2) <= parityCounts[1]
        parityToMod = {0: mod1, 1: mod2}

    for i in range(1, N + 1):
        mod = parityToMod[dist[i] % 2]
        if mod:
            assign[i] = mod.pop()
        else:
            assign[i] = mod0.pop()

print(" ".join(str(assign[i]) for i in range(1, N + 1)))

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




N = int(readline())

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

DIST = [-1] * (N+1)
STACK = [1]
DIST[1] = 0

'''
距離を求めて、2で割る
木ならこれでOK

while STACK:
    v = STACK.pop()

    for w in E[v]:
        if DIST[w] == -1:
            DIST[w] = DIST[v] + 1
            STACK.append(w)
'''

COLOR = [None] * (N + 1)


def setColor(v, c):
    COLOR[v] = c
    for w in E[v]:
        if COLOR[w] == None:
            setColor(w, -c)


setColor(1, 1)

EVEN = [i for i, x in enumerate(COLOR) if x == 1 and i > 0]
ODD = [i for i, x in enumerate(COLOR) if x == -1 and i > 0]

listN = list(range(1, N + 1))
mod1 = deque(listN[0::3])
mod2 = deque(listN[1::3])
mod0 = deque(listN[2::3])

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


def assign(target, arr1, arr2=[], arr3=[]):
    source = [arr1, arr2, arr3]
    idx = 0
    for e in target:
        if len(source[idx]) == 0:
            idx += 1

        ANS[e] = source[idx].pop()
    return 0


if len(EVEN) <= len(mod0):
    assign(EVEN, mod0)
    assign(ODD, mod0, mod1, mod2)
elif len(ODD) <= len(mod0):
    assign(ODD, mod0)
    assign(EVEN, mod0, mod1, mod2)
else:
    assign(EVEN, mod1, mod0)
    assign(ODD, mod2, mod0)

ANS = ANS[1:]
print(' '.join(map(str, ANS)))

Solution (Python):
N = int(input())

node = [[] for _ in range(N)]

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


group = [False] * N

parents = list(range(N))
stack = [0]


while stack:
    p = stack.pop()
    
    for c in node[p]:
        
        if c != parents[p]:
            
            parents[c] = p
            
            group[c] = not group[p]
            stack.append(c)

p = [0] * N
three = 3
if group.count(True) <= N // 3:
    other = 1
    
    for i in range(N):
        if not group[i] and other <= N:
            p[i] = other
            other += other % 3
        else:
            p[i] = three
            three += 3
elif group.count(False) <= N // 3:
    other = 1
    
    for i in range(N):
        if group[i] and other <= N:
            p[i] = other
            other += other % 3
        else:
            p[i] = three
            three += 3

else:
    one, two = 1, 2
    
    for i in range(N):
        if not group[i] and one <= N:
            p[i] = one
            one += 3
        elif group[i] and two <= N:
            p[i] = two
            two += 3
        else:
            p[i] = three
            three += 3
print(" ".join(map(str, p)))

Solution (Python):
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
x=[[],[],[]]
for i in range(n):
    x[i%3]+=i+1,
for a,b in zip(*[iter(t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
a=[-1]*n
p=a[:]
p[0]=0
s=[0]
c=[1,0]
while s:
    v=s.pop()
    for w in e[v]:
        if p[w]<0:
            p[w]=p[v]^1
            c[p[w]]+=1
            s+=w,
if min(c)<=n//3:
    x[0]+=x[1]
    f=c[0]<=n//3
    for i,v in enumerate(p):
        j=(v==f)-1
        a[i]=x[j if x[j]else-1].pop()
else:
    for i,v in enumerate(p):
        a[i]=x[v if x[v]else-1].pop()
print(*a)

Solution (Python):
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
x=[[],[],[]]
for i in range(n):
    x[i%3]+=i+1,
for a,b in zip(*[iter(t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
a=[-1]*n
p=a[:]
p[0]=0
s=[0]
c=[1,0]
while s:
    v=s.pop()
    for w in e[v]:
        if p[w]<0:
            p[w]=p[v]^1
            c[p[w]]+=1
            s+=w,
if min(c)<=n//3:
    x[0]+=x[1]
    f=c[0]<=n//3
    for i,v in enumerate(p):
        j=(v==f)-1
        a[i]=x[j if x[j]else-1].pop()
else:
    for i,v in enumerate(p):
        a[i]=x[v if x[v]else-1].pop()
print(*a)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import deque

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

    
    use = [-1 for _ in range(N)]
    d = [[0],[]]
    use[0] = 0
    q = deque([0])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if use[fol] == -1:
                use[fol] = (use[now]+1)%2
                q.append(fol)
                d[use[fol]].append(fol)

    ans = [0 for _ in range(N)]
    b = [False for _ in range(N)]
    if len(d[0]) <= N//3:
        l = len(d[0])
        for i in range(l):
            ans[d[0][i]] = 3*i+3
            b[3*i+2] = True
        t = 0
        for num in d[1]:
            while b[t]:
                t += 1
            ans[num] = t+1
            b[t] = True
    elif len(d[1]) <= N//3:
        l = len(d[1])
        for i in range(l):
            ans[d[1][i]] = 3*i+3
            b[3*i+2] = True
        t = 0
        for num in d[0]:
            while b[t]:
                t += 1
            ans[num] = t+1
            b[t] = True
    else:
        l = len(d[0])
        t = 0
        for i in range(l):
            if i < (N-1)//3+1:
                ans[d[0][i]] = 3*i+1
                b[3*i] = True
            else:
                ans[d[0][i]] = 3*t+3
                b[3*t+2] = True
                t += 1
        l = len(d[1])
        for i in range(l):
            if i < (N-2)//3+1:
                ans[d[1][i]] = 3*i+2
                b[3*i+1] = True
            else:
                ans[d[1][i]] = 3*t+3
                b[3*t+2] = True
                t += 1
    
    print(*ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

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

b = [[] for i in range(n)]
a1=[]
a2=[]
ans=[0]*n
for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)
    b[a[i][1]-1].append(a[i][0]-1)

import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)
        a1.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    if dis[y]%2==0:
                        a1.append(y)
                    else:
                        a2.append(y)
        return a1,a2
    return bfs()

tree(0)

j = 0
k = 0
if min(len(a1),len(a2))<=n//3:
    if len(a1)<=n//3:
        for i in range(1,n+1):
            if i<=len(a1)*3 and i%3==0 and j<=len(a1)-1:
                ans[a1[j]]=i
                j+=1
            else:
                ans[a2[k]]=i
                k+=1
    else:
        for i in range(1,n+1):
            if i<=len(a2)*3 and i%3==0 and j<=len(a2)-1:
                ans[a2[j]]=i
                j+=1
            else:
                ans[a1[k]]=i
                k+=1

else:
    for i in range(1,n+1):
        if i%3==1:
            ans[a1[j]]=i
            j+=1
        elif i%3==2:
            ans[a2[k]] = i
            k += 1
        else:
            continue

    for i in range(3,n+1,3):
        if j<=len(a1)-1:
            ans[a1[j]]=i
            j+=1
        else:
            ans[a2[k]] = i
            k += 1


print(*ans)

Solution (Python):


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

Solution (Python):
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()

Solution (Python):


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

Solution (Python):


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

Solution (Python):

 
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)
	

	
	depths=np.empty(n, np.bool)
	dfs(1, depths, 0, edge, -1)


	
	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]

	
	values=np.empty(n, int32)
	sum0=(depths==0).sum()
	sum1=(depths==1).sum()
	

	
	if sum0<=remainingMod[0]:

		values[depths==0]=0
		remainingMod[0]-=sum0
		remaining=np.concatenate([v*np.ones(remainingMod[v], int32) for v in range(3)])
		values[depths==1]=remaining
	
	elif sum1<=remainingMod[0]:

		values[depths==1]=0
		remainingMod[0]-=sum1
		remaining=np.concatenate([v*np.ones(remainingMod[v], int32) for v in range(3)])
		values[depths==0]=remaining
		
	else:

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































 
 
if __name__=="__main__":
	inputs=getInputs()

	main(inputs)

Solution (Python):
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)))

Solution (Python):
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)))

Solution (Python):
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  
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)

Solution (Python):
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


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



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)

Solution (Python):














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

    
    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)

    
    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)

    
    k = N // 3  
    g1 = iter(range(1, N + 1, 3))  
    g2 = iter(range(2, N + 1, 3))  
    g3 = iter(range(3, N + 1, 3))
    if size_0 <= k:  
        g123 = chain(g1, g2, g3)
        ret = (next(g3) if p == 0 else next(g123) for p in parity)

    elif N - size_0 <= k:  
        g123 = chain(g1, g2, g3)
        ret = (next(g3) if p == 1 else next(g123) for p in parity)

    else:  
        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()

Solution (Python):














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

    
    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)

    
    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)

    
    k = N // 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:
        
        
        for v in vs[0]:
            parity[v] = next(g3)  

        g123 = chain(g1, g2, g3)

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

    elif len(vs[1]) <= k:
        
        
        for v in vs[1]:
            parity[v] = next(g3)  

        g123 = chain(g1, g2, g3)

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

    else:
        
        
        

        g13 = chain(g1, g3)
        for v in vs[0]:
            parity[v] = next(g13)
            
            

        g23 = chain(g2, g3)
        for v in vs[1]:
            parity[v] = next(g23)
            
            

    print(*parity)


if __name__ == '__main__':
    main()