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):
import sys
 
sys.setrecursionlimit(10 ** 8)

n = int(input())

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

odd = []
even = []

ans = [-1] * n
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)

dfs(0)

nums = [[],[],[]]
for i in range(1,n+1):
    nums[i%3].append(i)

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[odd.pop()] = num
    for num in nums[2]:
        ans[even.pop()] = num
    rest = nums[0] + nums[1] + nums[2]
    for num in rest:
        if len(odd):
            ans[odd.pop()] = num
        elif len(even):
            ans[even.pop()] = num

print(*ans)

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

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


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

root = 1
rank = [0] * (N+1) 
rank[1] = 1
parent = [0] * (N+1) 
stack = [root]
while stack:
    cur = stack.pop()
    r = rank[cur]
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        rank[next] = r + 1
        stack.append(next)

counter = [0, 0]
for x in rank[1:]:
    counter[x%2] += 1
num0mod3 = N // 3
num1mod3 = (N+2) // 3
num2mod3 = (N+1) // 3
answer = [0] * (N+1)
if max(counter) >= num1mod3 + num2mod3:
    
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 1
            if cur % 3 == 0:
                cur += 1
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
else:
    
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 2
    for i in range(1, N+1):
        if rank[i] % 2 == 1-index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)

print(*answer[1:])

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1

"""

import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def Size(self,x):
        return self.size[self.find(x)]

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


n = onem()

tr = [[] for i in range(n)]
po = [0 for i in range(n)]

for i in range(n-1):
    a,b = m()
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)

de = cl.deque([[0,-1,0]])
bl = 0
re = 0
while de:
    data = de.popleft()
    if data[2] %2 == 0:
        po[data[0]] = 1
        re += 1
    else:
        po[data[0]] = 2
        bl += 1
    for i in range(len(tr[data[0]])):
        if tr[data[0]][i] != data[1]:
            de.append([tr[data[0]][i],data[0],data[2]+1])

tr = n // 3

b0 = cl.deque([(i+1)*3 for i in range(tr)])
b1 = cl.deque([(i)*3+1 for i in range(tr+(1 if n % 3 >= 1 else 0))])
b2 = cl.deque([(i)*3+2 for i in range(tr+(1 if n % 3 >= 2 else 0))])

if re <= tr:
    for i in range(n):
        if po[i] == 1:
            po[i] = b0.popleft()
        else:
            if len(b1) != 0:
                po[i] = b1.popleft()
            elif len(b2) != 0:
                po[i] = b2.popleft()
            else:
                po[i] = b0.popleft()

elif bl <= tr:
    for i in range(n):
        if po[i] == 2:
            po[i] = b0.popleft()
        else:
            if len(b1) != 0:
                po[i] = b1.popleft()
            elif len(b2) != 0:
                po[i] = b2.popleft()
            else:
                po[i] = b0.popleft()


else:
    for i in range(n):
        if po[i] == 1:
            if len(b1) != 0:
                po[i] = b1.popleft()
            else:
                po[i] = b0.popleft()
        else:
            if len(b2) != 0:
                po[i] = b2.popleft()
            else:
                po[i] = b0.popleft()



print(jo(po))

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)
    
    red, black = list(), list()
    visited = [False] * N
    stack = [(0, True)]
    visited[0] = True
    while stack:
        v, is_red = stack.pop()
        if is_red: red.append(v)
        else: black.append(v)
        for to in G[v]:
            if visited[to]: continue
            visited[to] = True
            stack.append((to, not is_red))
    if len(red) < len(black): red, black = black, red

    ans = [0] * N
    if len(black) <= N//3:
        n3 = 3
        for v in black: ans[v], n3 = n3, n3 + 3
        n = 1
        for v in red:
            if n3 <= N: ans[v], n3 = n3, n3 + 3
            else:
                ans[v], n = n, n + 1
                if n%3 == 0: n += 1
    else:
        n1, n2, n3 = 1, 2, 3
        for v in black:
            if n1 <= N: ans[v], n1 = n1, n1 + 3
            else: ans[v], n3 = n3, n3 + 3
        for v in red:
            if n2 <= N: ans[v], n2 = n2, n2 + 3
            else: ans[v], n3 = n3, n3 + 3
    print(*ans)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

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

color = [-1] * n
def dfs(p, v, c):
    for nv in edge[v]:
        color[nv] = not c
        if nv == p:
            continue
        dfs(v, nv, not c)

dfs(-1, 0, 0)
white = sum(color)
black = n - white
if white > black:
    white, black = black, white
    color = [not item for item in color]


if white <= n // 3:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    others = [item for item in range(1, n+1) if item % 3 != 0]
    array = deque(others + threes)

else:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    twos = [item for item in range(1, n+1) if item % 3 == 2]
    ones = [item for item in range(1, n+1) if item % 3 == 1]
    array = deque(ones + threes + twos)

ans = [-1] * n
for i, is_white in enumerate(color):
    if is_white:
        ans[i] = array.pop()
    else:
        ans[i] = array.popleft()

print(*ans)

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








from collections import deque
from collections import defaultdict


def main():
	N=int(input())
	M=N-1
	G = defaultdict(set)

	color = [0 for i in range(N + 1)]

	for _ in range(M):
		A, B = map(int, input().split())
		G[A].add(B)
		G[B].add(A)

	color[1] = 1
	que = deque([1])  

	while len(que):
		p = que.popleft()  
		for q in list(G[p]):  
			if color[q] == 0:  
				color[q] = -color[p]
				que.append(q)


	b=[]
	w=[]
	for i in range(1,N+1):
		if color[i]==1:
			b.append(i)
		else:
			w.append(i)

	ans=[0]*(N+1)
	lim = ((N - 1) // 3)
	i=0
	if len(b)<len(w):
		for val in w:
			if i<=lim:
				ans[val]=3*i+1
				i+=1
			else:
				break
		w=w[i:]
	else:
		for val in b:
			if i<=lim:
				ans[val]=3*i+1
				i+=1
			else:
				break
		b=b[i:]


	lim = ((N - 2) // 3)
	i=0
	if len(b)<len(w):
		for val in w:
			if i<=lim:
				ans[val]=3*i+2
				i+=1
			else:
				break
		w=w[i:]
	else:
		for val in b:
			if i<=lim:
				ans[val]=3*i+2
				i+=1
			else:
				break
		b=b[i:]


	i=0
	for val in b:
		ans[val]=3*i+3
		i+=1
	for val in w:
		ans[val]=3*i+3
		i+=1




	print(*ans[1:])




if __name__ == "__main__":
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())

g = [[] for _ in range(n)]

ans = [-1] * n
odd = []
even = []
nums = [[], [], []]
for i in range(1, n + 1):
    nums[i % 3].append(i)

def dfs(v, p = -1, d = 0):
    if d % 2:
        odd.append(v)
    else:
        even.append(v)

    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, d + 1)

for i in range(n - 1): 
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[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 odd_node in odd:
        if len(nums[1]) != 0:
            ans[odd_node] = nums[1].pop()
        else:
            ans[odd_node] = nums[0].pop()
    for even_node in even:
        if len(nums[2]) != 0:
            ans[even_node] = nums[2].pop()
        else:
            ans[even_node] = nums[0].pop()

print(*ans)

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

n = int(input())

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

used = [0]*n
tank = [0]
used[0] = 1
ca = 0
cb = 0
while tank:
    p = tank.pop()
    if used[p] > 0:
        ca += 1
    for e in edge[p]:
        if used[e] == 0:
            used[e] = -used[p]
            tank.append(e)
cb = n-ca
res = [0]*n
flag = [True]*(n+2)

if ca <= n//3:
    tmp = 0
    for i in range(n):
        if used[i] == 1:
            tmp += 3
            res[i] = tmp
            flag[tmp] = False
    tmp = 1
    for i in range(n):
        if used[i] != 1:
            res[i] = tmp
            flag[tmp] = False
            while not flag[tmp]:
                tmp += 1
    print(*res)
elif cb <= n//3:
    tmp = 0
    for i in range(n):
        if used[i] == -1:
            tmp += 3
            res[i] = tmp
            flag[tmp] = False
    tmp = 1
    for i in range(n):
        if used[i] != -1:
            res[i] = tmp
            flag[tmp] = False
            while not flag[tmp]:
                tmp += 1
    print(*res)
else:
    tmp = -2
    for i in range(n):
        if used[i] == -1:
            tmp += 3
            if tmp > n:
                tmp = 3
            res[i] = tmp
            flag[tmp] = False
    tmp = 2
    for i in range(n):
        if used[i] != -1:
            res[i] = tmp
            flag[tmp] = False
            while not flag[tmp]:
                tmp += 1
                if tmp > n:
                    tmp = 3
                    break
    print(*res)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)


ans = [-1]*(n+1)
q = [1]
ans[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if ans[next] == -1:
            q.append(next)
            ans[next] = (ans[now]+1)%2

if ans.count(1) <= n//3:
    three = set([3*i+3 for i in range(n//3)])
    onetwo = set([i+1 for i in range(n)])
    onetwo = onetwo - three
    three = list(three)
    three.sort()
    onetwo = list(onetwo)
    onetwo.sort()
    three_ind = 0
    onetwo_ind = 0
    for i in range(1, n+1):
        if ans[i] == 1:
            ans[i] = three[three_ind]
            three_ind += 1
        else:
            if onetwo_ind >= len(onetwo):
                ans[i] = three[three_ind]
                three_ind += 1
            else:
                ans[i] = onetwo[onetwo_ind]
                onetwo_ind += 1

elif ans.count(0) <= n//3:
    three = set([3*i+3 for i in range(n//3)])
    onetwo = set([i+1 for i in range(n)])
    onetwo = onetwo - three
    three = list(three)
    three.sort()
    onetwo = list(onetwo)
    onetwo.sort()
    three_ind = 0
    onetwo_ind = 0
    for i in range(1, n+1):
        if ans[i] == 0:
            ans[i] = three[three_ind]
            three_ind += 1
        else:
            if onetwo_ind >= len(onetwo):
                ans[i] = three[three_ind]
                three_ind += 1
            else:
                ans[i] = onetwo[onetwo_ind]
                onetwo_ind += 1

else:
    zero = 0
    one = 0
    two = 0
    for i in range(1, n+1):
        if ans[i] == 0:
            ans[i] = zero*3+1
            zero += 1
        elif ans[i] == 1:
            ans[i] = one*3+2
            one += 1

    three = 0
    for i in range(1, n+1):
        if ans[i] > n:
            ans[i] = three*3+3
            three += 1

print(" ".join(map(str, ans[1:])))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

g1 = []
g2 = []
for i,d in enumerate(depth):
    if d%2:
        g2.append(i)
    else:
        g1.append(i)
if len(g1) < len(g2):
    g1,g2 = g2,g1

ans = [None] * N
if len(g2) <= N//3:
    for n in range(1,N+1):
        if n%3==0:
            if g2:
                i = g2.pop()
            else:
                i = g1.pop()
        else:
            i = g1.pop()
        ans[i] = n
else:
    for n in range(1,N+1,3):
        i = g1.pop()
        ans[i] = n
    for n in range(2,N+1,3):
        i = g2.pop()
        ans[i] = n
    for n in range(3,N+1,3):
        if g1:
            i = g1.pop()
        else:
            i = g2.pop()
        ans[i] = n
print(*ans)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n = int(input())
G = [[] for i in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b-=1
  G[a].append(b)
  G[b].append(a)
ans = [0] * n
color = [[],[]]
def coloring(node,pre,oddeven):
  color[oddeven%2].append(node)
  for vi in G[node]:
    if vi != pre:
      coloring(vi,node,oddeven+1)
  return

coloring(0,-1,0)
A = n//3 + int(bool(n%3))
B = n//3 + int(n%3 == 2)
C = n//3

a=b=0; c=1
if len(color[0]) >= A and len(color[1]) >= B:
  for i,ci in enumerate(color[0]):
    if i < A:
      ans[ci] = 3 * i + 1
    else:
      ans[ci] = 3 * c
      c += 1

  for i,ci in enumerate(color[1]):
    if i < B:
      ans[ci] = 3 * i + 2
    else:
      ans[ci] = 3 * c
      c += 1

elif len(color[0]) < A:
  
  
  for i ,ci in enumerate(color[0]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[1]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

else:
  
  
  for i ,ci in enumerate(color[1]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[0]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

print(*ans)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n = int(input())
G = [[] for i in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b-=1
  G[a].append(b)
  G[b].append(a)
ans = [0] * n
color = [[],[]]
def coloring(node,pre,oddeven):
  color[oddeven%2].append(node)
  for vi in G[node]:
    if vi != pre:
      coloring(vi,node,oddeven+1)
  return

coloring(0,-1,0)
A = n//3 + int(bool(n%3))
B = n//3 + int(n%3 == 2)
C = n//3



a=b=0; c=1
if len(color[0]) > C and len(color[1]) > C:
  for i,ci in enumerate(color[0]):
    if i < A:
      ans[ci] = 3 * i + 1
    else:
      ans[ci] = 3 * c
      c += 1

  for i,ci in enumerate(color[1]):
    if i < B:
      ans[ci] = 3 * i + 2
    else:
      ans[ci] = 3 * c
      c += 1

elif len(color[0]) <= C:
  
  
  for i ,ci in enumerate(color[0]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[1]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

else:
  
  
  for i ,ci in enumerate(color[1]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[0]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

print(*ans)

Solution (Python):
from collections import deque


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    group = [set() for _ in range(2)]
    q = deque([(0, 0, -1)])
    while len(q):
        cur, g, prev = q.popleft()
        group[g].add(cur)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, 1-g, cur))
    if len(group[0]) > len(group[1]):
        tmp = group[0]
        group[0] = group[1]
        group[1] = tmp
    ans = [0] * N
    pool = set(range(1, N+1))
    if len(group[0]) <= N//3:
        for i, x in enumerate(group[0]):
            ans[x] = (i+1)*3
            pool.remove((i+1)*3)
        for x in group[1]:
            ans[x] = pool.pop()
    else:
        cand = (list(range(1, N+1, 3)) +
                list(range(3, N+1, 3)))[:len(group[0])]
        for x, v in zip(group[0], cand):
            ans[x] = v
            pool.remove(v)
        for x in group[1]:
            ans[x] = pool.pop()
    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def main():

    N = int(input())
    g = {}
    for i in range(N):
        g[i] = set()

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

    
    dist = [-1] * N     
    dist[0] = 0
    n_even = 0
    que = deque([0])
    while len(que):
        v = que[0]
        if dist[v] % 2 == 0:
            n_even += 1
        que.popleft()
        for n in g[v]:
            if dist[n] == -1:
                dist[n] = (dist[v] + 1) % 2
                que.append(n)

    ans = [-1] * N
    if n_even <= int(N / 3):
        n3, n3q, n3r = 1, 0, 1
        for i in range(N):
            if dist[i] == 0:
                ans[i] = n3 * 3
                n3 += 1
            else:
                if n3q * 3 + n3r <= N:
                    ans[i] = n3q * 3 + n3r
                    if n3r == 1:
                        n3r = 2
                    else:
                        n3q += 1
                        n3r = 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
    elif n_even > int(N * 2 / 3):
        n3, n3q, n3r = 1, 0, 1
        for i in range(N):
            if dist[i] == 1:
                ans[i] = n3 * 3
                n3 += 1
            else:
                if n3q * 3 + n3r <= N:
                    ans[i] = n3q * 3 + n3r
                    if n3r == 1:
                        n3r = 2
                    else:
                        n3q += 1
                        n3r = 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
    else:
        n3, n31, n32 = 1, 0, 0
        for i in range(N):
            if dist[i] == 0:
                if n31 * 3 + 1 <= N:
                    ans[i] = n31 * 3 + 1
                    n31 += 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
            else:
                if n32 * 3 + 2 <= N:
                    ans[i] = n32 * 3 + 2
                    n32 += 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def main():

    N = int(input())
    g = {}
    for i in range(N):
        g[i] = set()

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

    
    dist = [-1] * N     
    dist[0] = 0
    n_even = 0
    que = deque([0])
    while len(que):
        v = que[0]
        if dist[v] % 2 == 0:
            n_even += 1
        que.popleft()
        for n in g[v]:
            if dist[n] == -1:
                dist[n] = (dist[v] + 1) % 2
                que.append(n)

    ans = [-1] * N
    if n_even <= int(N / 3):
        n3, n3q, n3r = 1, 0, 1
        for i in range(N):
            if dist[i] == 0:
                ans[i] = n3 * 3
                n3 += 1
            else:
                if n3q * 3 + n3r <= N:
                    ans[i] = n3q * 3 + n3r
                    if n3r == 1:
                        n3r = 2
                    else:
                        n3q += 1
                        n3r = 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
    elif n_even > int(N * 2 / 3):
        n3, n3q, n3r = 1, 0, 1
        for i in range(N):
            if dist[i] == 1:
                ans[i] = n3 * 3
                n3 += 1
            else:
                if n3q * 3 + n3r <= N:
                    ans[i] = n3q * 3 + n3r
                    if n3r == 1:
                        n3r = 2
                    else:
                        n3q += 1
                        n3r = 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
    else:
        n3, n31, n32 = 1, 0, 0
        for i in range(N):
            if dist[i] == 0:
                if n31 * 3 + 1 <= N:
                    ans[i] = n31 * 3 + 1
                    n31 += 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
            else:
                if n32 * 3 + 2 <= N:
                    ans[i] = n32 * 3 + 2
                    n32 += 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

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

lst = [[], [], []]
for i in range(1, n+1):
    lst[i % 3].append(i)

p = [0]*n

depth = [-1]*n
depth[0] = 0

q = [0]

cnt = [1, 0]

while q:
    v = q.pop()
    for w in g[v]:
        if depth[w] != -1:
            continue
        depth[w] = depth[v] + 1
        cnt[depth[w] % 2] += 1
        q.append(w)


ans = [0]*n

if cnt[0] <= n//3:
    ans[0] = lst[0].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 == 0:
                ans[w] = lst[0].pop()
            else:
                if lst[1]:
                    ans[w] = lst[1].pop()
                elif lst[2]:
                    ans[w] = lst[2].pop()
                else:
                    ans[w] = lst[0].pop()
            q.append(w)
elif cnt[1] <= n//3:
    ans[0] = lst[1].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 != 0:
                ans[w] = lst[0].pop()
            else:
                if lst[1]:
                    ans[w] = lst[1].pop()
                elif lst[2]:
                    ans[w] = lst[2].pop()
                else:
                    ans[w] = lst[0].pop()
            q.append(w)
else:
    ans[0] = lst[2].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 != 0:
                if lst[1]:
                    ans[w] = lst[1].pop()
                else:
                    ans[w] = lst[0].pop()
            else:
                if lst[2]:
                    ans[w] = lst[2].pop()
                else:
                    ans[w] = lst[0].pop()
            q.append(w)

print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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



adj_list = [[] for _ in range(N+1)]

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



group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    
    
    
    
    nxt_grp = grp^3
    
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    
    
    
if min(group_num) <= N//3:
    
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in enumerate(group):
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in enumerate(group):
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            if idx_1>N:continue
            ans[i] = idx_1
            used[idx_1] = True
            idx_1 += 3
        else:
            if idx_2>N:continue
            ans[i] = idx_2
            used[idx_2] = True
            idx_2 += 3

    idx = 3
    for i in range(1,N+1):
        if ans[i]==0:
            while used[idx]:
                idx += 3
            ans[i] = idx
            used[idx] = True

    print(*ans[1:])