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 queue

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n-1)]
num_0_mod_3 = n // 3
num_2_mod_3 = (n+1) // 3
num_1_mod_3 = (n+2) // 3


def add_edge(u, v ):
    G[u].append(v)
    G[v].append(u)

G = [[] for _ in range(n)] 
for edge in edges:
    add_edge(edge[0]-1, edge[1]-1)

num_distance_even = 0
num_distance_odd = 0

q = queue.Queue()
q.put(0)

distance = [-1] * n
distance[0] = 0
num_distance_even += 1

for v in G[0]:
    q.put(v)

while(q.qsize() > 0):
    now = q.get()
    for v in G[now]:
        if distance[v] >= 0:
            pass
        else:
            q.put(v)
            distance[v] = distance[now] + 1
            if (distance[v] & 1):
                num_distance_odd += 1
            else:
                num_distance_even += 1




ans = [-1] * n

index_one = 1
index_two = 2
index_zero = 3

if num_distance_even >= num_1_mod_3 + num_2_mod_3:
    

    for i in range(n):
        if (distance[i] & 1) == 1:
            ans[i] = index_zero
            index_zero += 3
        else:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            elif (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


elif num_distance_odd >= num_1_mod_3 + num_2_mod_3:
    
    for i in range(n):
        if (distance[i] & 1) == 0:
            ans[i] = index_zero
            index_zero += 3
        else:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            elif (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


else:

    
    for i in range(n):
        if (distance[i] & 1) == 1:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            else:
                ans[i] = index_zero
                index_zero += 3
        else:
            if (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


print(' '.join(list(map(str, 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





def eulerian_trail(tree, max_v, root=0):
    """
    木のオイラー路; オイラーツアー
    :param list of (list of (int, int)) tree:
    :param int max_v:
    :param int root:
    :return: (trails, depths, weights)
    :rtype: (list of int, list of int, list of int)
    """
    seen = [False] * (max_v + 1)
    
    trails = []
    
    depths = []
    
    weights = []
    
    stack = [(root, 0, 0, True)]
    while stack:
        v, d, w, forward = stack.pop()
        seen[v] = True
        trails.append(v)
        depths.append(d)
        weights.append(w)
        if not forward:
            continue

        for u, w in tree[v]:
            if not seen[u]:
                stack.append((v, d, -w, False))
                stack.append((u, d + 1, w, True))
    return trails, depths, weights


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, 1))
    graph[b].append((a, 1))

counts = [N // 3, (N + 2) // 3, (N + 1) // 3]


vs, _, _ = eulerian_trail(graph, N - 1)
bp = [0] * N
for i, v in enumerate(vs):
    bp[v] = i & 1


ansmod = [-1] * N
if bp.count(0) <= counts[0]:
    
    for v, b in enumerate(bp):
        if b == 0 and counts[0] > 0:
            ansmod[v] = 0
            counts[0] -= 1
elif bp.count(1) <= counts[0]:
    
    for v, b in enumerate(bp):
        if b == 1 and counts[0] > 0:
            ansmod[v] = 0
            counts[0] -= 1
else:
    
    for v, b in enumerate(bp):
        if b == 0 and counts[1] > 0:
            ansmod[v] = 1
            counts[1] -= 1
        if b == 1 and counts[2] > 0:
            ansmod[v] = 2
            counts[2] -= 1

for v in range(N):
    if ansmod[v] < 0:
        for i in range(3):
            if counts[i] > 0:
                ansmod[v] = i
                counts[i] -= 1
                break

ans = []
M = [3, 1, 2]
for a in ansmod:
    ans.append(M[a])
    M[a] += 3
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 // 2
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
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

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

grand_sum = [0 for _ in range(n)]
for i in range(n):
	grand_sum[i] = sum([len(adj[x]) for x in adj[i]]) - len(adj[i])

if n <= 3:
	print(*list(range(1, n+1)))
	sys.exit()

ans = [-1 for _ in range(n)]


tri = [0 for _ in range(n)]
for a, b in edges:
	tri[b] += grand_sum[a] - len(adj[b]) + 1
	tri[a] += grand_sum[b] - len(adj[a]) + 1
	
	
	











flg = False
orig = -1
for i, t in enumerate(tri):
	if t >= n - (n//3):
		flg = True
		orig = i


signs = [-1 for _ in range(n)]
def dfs(x):
	for v in adj[x]:
		if signs[v] < 0:
			signs[v] = 1 ^ signs[x]
			dfs(v)

signs[0] = 0
dfs(0)

if flg:
	cur = [1, 2, 3]
	for i in range(n):
		if signs[i] == signs[orig]:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] <= n:
			ans[i] = cur[0]
			cur[0] += 3
		elif cur[1] <= n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[2]
			cur[2] += 3
	print(*ans)
	sys.exit()

num1 = sum(signs)
num2 = n - num1



M, m = max(num1, num2), min(num1, num2) 

if max(num1, num2) >= n - (n // 3):
	if num1 > num2:
		more = 0
	else:
		more = 1
	cur = [1, 2, 3]
	for i in range(n):
		if signs[i] == more:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] <= n:
			ans[i] = cur[0]
			cur[0] += 3
		elif cur[1] <= n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[2]
			cur[2] += 3
	print(*ans)
	sys.exit()




if num1 > num2:
	one, two = num1, num2
	more = 1
else:
	one, two = num2, num1
	more = 0
cur = [2, 1, 3]
for i in range(n):
	if ans[i] > 0:
		continue
	if signs[i] == more:
		if cur[1] > n and cur[2] <= n: 
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[1] > n and cur[2] > n:
			ans[i] = cur[0]
			cur[0] += 3
		else:
			ans[i] = cur[1]
			cur[1] += 3
	else:
		if cur[0] > n and cur[2] <= n:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] > n and cur[2] > n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[0]
			cur[0] += 3
print(*ans)

Solution (Python):


import queue

def main():

    n = int(input())
    edges = [list(map(int, input().split())) for _ in range(n-1)]
    num_0_mod_3 = n // 3
    num_2_mod_3 = (n+1) // 3
    num_1_mod_3 = (n+2) // 3


    def add_edge(u, v ):
        G[u].append(v)
        G[v].append(u)

    G = [[] for _ in range(n)] 
    for edge in edges:
        add_edge(edge[0]-1, edge[1]-1)

    num_distance_even = 0
    num_distance_odd = 0

    q = queue.Queue()
    q.put(0)

    distance = [-1] * n
    distance[0] = 0
    num_distance_even += 1

    for v in G[0]:
        q.put(v)

    while(q.qsize() > 0):
        now = q.get()
        for v in G[now]:
            if distance[v] >= 0:
                pass
            else:
                q.put(v)
                distance[v] = distance[now] + 1
                if (distance[v] & 1):
                    num_distance_odd += 1
                else:
                    num_distance_even += 1

    
    

    ans = [-1] * n

    index_one = 1
    index_two = 2
    index_zero = 3

    if num_distance_even >= num_1_mod_3 + num_2_mod_3:
        

        for i in range(n):
            if (distance[i] & 1) == 1:
                ans[i] = index_zero
                index_zero += 3
            else:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                elif (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3


    elif num_distance_odd >= num_1_mod_3 + num_2_mod_3:
        
        for i in range(n):
            if (distance[i] & 1) == 0:
                ans[i] = index_zero
                index_zero += 3
            else:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                elif (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3

    else:
    
        
        for i in range(n):
            if (distance[i] & 1) == 1:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3
            else:
                if (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import math

N = int(input())
side = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    side[b-1].append(a-1)
ans = [0]*N
ans[0] = 1
queue = deque([0])
count = [0,1,0]
while queue:
    q = queue.popleft()
    for i in side[q]:
        if ans[i] == 0:
            ans[i] = ans[q]%2 + 1
            count[ans[i]] += 1
            queue.append(i)
if max(count) <=N - (N+1)//3:
    X = [3,2,2]
    X[count.index(max(count))] = 1
    for i in range(N):
        if X[ans[i]] <= N:
            X[ans[i]] += 3
            ans[i] = X[ans[i]]-3
        else:
            ans[i] = X[0]
            X[0] += 3
else:
    Y = 3 - count.index(max(count))
    Z = 3 - Y
    X = 3
    for i in range(N):
        if ans[i] == Y:
            ans[i] = X
            X += 3
    W = 1
    for i in range(N):
        if ans[i] == Z:
            ans[i] = W
            W += 1
            if W%3 == 0 and W < X:
                W += 1
print(*ans)

Solution (Python):
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
seen = [0 for _ in range(n)]
clr = [2 for _ in range(n)]
seen[0] = 1
clr[0] = 0
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        now.append(y)
        clr[y] = 1 - clr[x]


a = n - sum(clr)
b = sum(clr)
z1 = 1
z2 = 2
z3 = 3
g1 = (n+2)//3
g2 = (n+1)//3
g3 = n//3

ans = [0 for _ in range(n)]
if a > g3 and b > g3:
  for i in range(n):
    if clr[i] == 0:
      if g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z3
        z3 += 3
    else:
      if g2:
        ans[i] = z2
        z2 += 3
        g2 -= 1
      else:
        ans[i] = z3
        z3 += 3
elif a <= g3:
  g3 -= a
  for i in range(n):
    if clr[i] == 0:
      ans[i] = z3
      z3 += 3
    else:
      if g3:
        ans[i] = z3
        z3 += 3
        g3 -= 1
      elif g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z2
        z2 += 3
elif b <= g3:
  g3 -= b
  for i in range(n):
    if clr[i] == 1:
      ans[i] = z3
      z3 += 3
    else:
      if g3:
        ans[i] = z3
        z3 += 3
        g3 -= 1
      elif g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z2
        z2 += 3
else:
  err
print(' '.join(map(str,ans)))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(250000)
l=[None]*N
g=[1,0]
def hu(n,c):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            g[c%2]+=1
            hu(i,c+1)
l[0]=0
hu(0,1)
a=[1,2,3]
if min(g)>N//3:
    b,c=0,1
    for i in l:
        if i%2:
            print(a[b],end=" ")
            a[b]+=3    
            if a[b]>N:
                b=2
        else:
            print(a[c],end=" ")
            a[c]+=3
            if a[c]>N:
                c=2
else:
    if g[0]<g[1]:
        b,c=0,2
        for i in l:
            if i%2:
                print(a[b],end=" ")
                a[b]+=3
                if a[b]>N:
                    if b==0:
                        b=1
                    else:
                        b=2
            else:
                print(a[c],end=" ")
                a[c]+=3
    else:
        b,c=0,2
        for i in l:
            if not i%2:
                print(a[b],end=" ")
                a[b]+=3
                if a[b]>N:
                    if b==0:
                        b=1
                    else:
                        b=2
            else:
                print(a[c],end=" ")
                a[c]+=3

Solution (Python):
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''





n = int(input())
es = []
nb = [[] for i in range(n)]

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


side = [[],[]]
checked = [-1 for i in range(n)]

queue = [0]
side[0].append(0)
checked[0] = 0
fin = 0

while(True):
    if(len(queue) == fin):
        break
    seeing = queue[fin]
    fin+=1
    
    for j in range(len(nb[seeing])):
        nextval = nb[seeing][j]
        if(checked[nextval]==-1):
            nextside =1 - checked[seeing]
            checked[nextval] = nextside
            side[nextside].append(nextval)
            queue.append(nextval)


nums3 = [n//3,n//3,n//3]

if(n%3 >= 1):
    nums3[0]+=1
if(n%3 == 2):
    nums3[1]+=1




ans = [-1 for i in range(n)]

if(len(side[0]) <= nums3[2]):
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    non3 = []
    for i in range(n):
        if((i+1)%3 != 0):
            non3.append(i+1)
    
    for i in range(cou0):
        ans[side[0][i]] = 3 + 3*i
    for j in range(nums3[2] - cou0):
        ans[side[1][j]] = 3 + 3*(j+cou0)
    startnum = nums3[2] - cou0
    for j in range(cou1 - startnum):
        ans[side[1][startnum+j]] = non3[j]
    
    
    
elif(len(side[1]) <= nums3[2]):
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    non3 = []
    for i in range(n):
        if((i+1)%3 != 0):
            non3.append(i+1)
    
    for i in range(cou1):
        ans[side[1][i]] = 3 + 3*i
    for j in range(nums3[2] - cou1):
        ans[side[0][j]] = 3 + 3*(j+cou1)
    startnum = nums3[2] - cou1
    for j in range(cou0 - startnum):
        ans[side[0][startnum+j]] = non3[j]
        

    
else:
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    for i in range(nums3[0]):
        ans[side[0][i]] = 1 + 3*i
        
    for i in range(nums3[1]):
        ans[side[1][i]] = 2 + 3*i
        
    start0 = nums3[0]
    done0 = cou0 - nums3[0]
    start1 = nums3[1]
    done1 = cou1 - nums3[1]
    for i in range(done0):
        ans[side[0][start0 + i]] = 3 + 3 * i
    for i in range(done1):
        ans[side[1][start1 + i]] = 3 + 3 * (i + done0)

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

Solution (Python):
n=int(input())
ans=[0]*n
three=n//3
two=(n-three)//2
one=n-three-two
t=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  t[a].append(b)
  t[b].append(a)
th=[]
Q=[0]
visited={0}
ma=0
thi=-1
while Q:
  th.append(Q)
  if len(Q)>ma:
    ma=len(Q)
    thi=len(th)-1
  P=[]
  for j in Q:
    for i in t[j]:
      if i not in visited:
        P.append(i)
        visited.add(i)
  Q=P
odd=even=0
for i in range(len(th)):
  if i%2==1:odd+=len(th[i])
  else:even+=len(th[i])
if odd>one+three:
  flag="error"
  d=0
elif even>one+three:
  flag="error"
  d=1
else:
  flag="normal"

if flag=="error":
  sudenideta=set()
  num=3
  for i in range(d,len(th),2):
    for j in th[i]:
      ans[j]=num
      sudenideta.add(num)
      num+=3
  num=1
  for i in range(d^1,len(th),2):
    for j in th[i]:
      while num in sudenideta:num+=1
      ans[j]=num
      sudenideta.add(num)
      num+=1
else:
  odd_num=2
  even_num=1
  three_num=3
  for i in range(len(th)):
    for j in th[i]:
      if i%2==1:
        if odd_num>n:
          ans[j]=three_num
          three_num+=3
        else:
          ans[j]=odd_num
          odd_num+=3
      else:
        if even_num>n:
          ans[j]=three_num
          three_num+=3
        else:
          ans[j]=even_num
          even_num+=3
print(*ans)

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

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  a, b = map(int, input().split())
  vec[a-1].append(b-1)
  vec[b-1].append(a-1)
  
q = [(0, -1, 0)]
dist = [0] * N
cnt = [0, 0]
while q :
  cur, pre, cost = q.pop()
  dist[cur] = cost
  cnt[cost] += 1
  for nex in vec[cur] :
    if nex != pre :
      q.append((nex, cur, cost ^ 1))

one = 1
two = 2
three = 3
if cnt[0] < (N + 2) // 3 :
  for i in range(N) :
    if dist[i] == 0 :
      dist[i] = three
      three += 3
    elif one <= N :
      dist[i] = one
      one += 3
    elif two <= N :
      dist[i] = two
      two += 3
    else :
      dist[i] = three
      three += 3
      
elif cnt[1] < (N + 1) // 3 :
  for i in range(N) :
    if dist[i] == 1 :
      dist[i] = three
      three += 3
    elif one <= N :
      dist[i] = one
      one += 3
    elif two <= N :
      dist[i] = two
      two += 3
    else :
      dist[i] = three
      three += 3
      
else :
  for i in range(N) :
    if dist[i] == 0 and one <= N :
      dist[i] = one
      one += 3
    elif dist[i] == 1 and two <= N :
      dist[i] = two
      two += 3
    else :
      dist[i] = three
      three += 3
      
print(*dist)

Solution (Python):
class Tree:
    def __init__(self, N):
        self.N = N 
        self.D = (self.N-1).bit_length() 
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def lca_initialize(self):
        self.dfs(0)
        self.doubling()
    
    def dfs(self, root):
        
        
        
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)
    
    def doubling(self):
        
        self.next = [[-1] * self.N for _ in range(self.D)]
        for v in range(self.N):
            self.next[0][v] = self.parent[v]
        for d in range(self.D - 1):
            for v in range(self.N):
                if self.next[d][v] != -1:
                    self.next[d + 1][v] = self.next[d][self.next[d][v]]
    
    def lca(self, u, v):
        
        
        if self.depth[u] > self.depth[v]: u, v = v, u
        
        diff = self.depth[v] - self.depth[u]
        for i in range(diff.bit_length()):
            if diff & (1 << i): v = self.next[i][v]
        if u == v: return u
        for i in range(self.depth[u].bit_length() - 1, -1, -1):
            pu, pv = self.next[i][u], self.next[i][v]
            if pu != pv: u, v = pu, pv
        return self.next[0][u]

N = int(input())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(0)
d_odd, d_even = [], []
rem = [[] for _ in range(3)]
for i in range(N):
    if tr.depth[i] % 2 == 0: d_even.append(i)
    else: d_odd.append(i)
    rem[(i+1)%3].append(i+1)
P = [0] * N
if len(d_odd) < len(d_even):
    if len(d_odd) <= len(rem[0]):
        for i in d_odd: P[i] = rem[0].pop()
    else:
        for i in d_odd:
            if rem[2]:
                P[i] = rem[2].pop()
            else:
                P[i] = rem[0].pop()
    temp = rem[2] + rem[0] + rem[1]
    for i in d_even: P[i] = temp.pop()
else:
    if len(d_even) <= len(rem[0]):
        for i in d_even: P[i] = rem[0].pop()
    else:
        for i in d_even:
            if rem[2]:
                P[i] = rem[2].pop()
            else:
                P[i] = rem[0].pop()
    temp = rem[2] + rem[0] + rem[1]
    for i in d_odd: P[i] = temp.pop()
print(*P)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return input().split()
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    def f(point, pre):
        p = lis[point]
        for nex in edg[point]:
            if nex == pre:
                continue
            lis[nex] = p + 1
            f(nex, point)
        return
    n = II()
    ab = LIR_(n - 1)
    lis = [-1] * n
    edg = [[] for _ in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    lis[0] = 1
    f(0, -1)
    d = [0, 0]
    for i in lis:
        d[i & 1] += 1
    ans = [None] * n
    if d[0] <= n // 3:
        t = 1
        for i in range(n):
            if lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 1
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    elif d[1] <= n // 3:
        t = 1
        for i in range(n):
            if not lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 1
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    else:
        t = n // 3
        odd = 1
        even = 2
        for i in range(n):
            if t:
                if lis[i] & 1:
                    if d[1] <= n // 3 + (n % 3 >= 1):
                        ans[i] = str(odd)
                        odd += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
                        d[1] -= 1
                else:
                    if d[0] <= n // 3 + (n % 3 >= 2):
                        ans[i] = str(even)
                        even += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
                        d[0] -= 1 
            else:
                if lis[i] & 1:
                    ans[i] = str(odd)
                    odd += 3
                else:
                    ans[i] = str(even)
                    even += 3
    print(" ".join(ans))


    return



if __name__ == '__main__':
    solve()

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

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

    from collections import deque
    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    one_num = 0
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] ^ 1
                if seen[u]:
                    one_num += 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()
    two_num = N - one_num

    one = list(range(1, N+1, 3))
    two = list(range(2, N+1, 3))
    three = list(range(3, N+1, 3))
    three_num = N // 3

    ans = [0] * (N+1)
    if one_num <= three_num:
        for v in range(1, N+1):
            if seen[v]:
                ans[v] = three.pop()
            else:
                if one:
                    ans[v] = one.pop()
                elif two:
                    ans[v] = two.pop()
                else:
                    ans[v] = three.pop()
    elif two_num <= three_num:
        for v in range(1, N+1):
            if not seen[v]:
                ans[v] = three.pop()
            else:
                if one:
                    ans[v] = one.pop()
                elif two:
                    ans[v] = two.pop()
                else:
                    ans[v] = three.pop()
    else:
        for v in range(1, N+1):
            if seen[v]:
                if one:
                    ans[v] = one.pop()
                else:
                    ans[v] = three.pop()
            else:
                if two:
                    ans[v] = two.pop()
                else:
                    ans[v] = three.pop()
    print(*ans[1:])


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(u=0,pu=-1,color=0):
        cc[u]=color
        cntc[color]+=1
        for cu in to1[u]:
            if pu==cu:continue
            dfs(cu,u,1-color)


    n=II()
    to1=[set() for _ in range(n)]
    cc=[0]*n
    cntc=[0]*2
    for _ in range(n-1):
        a,b=MI1()
        to1[a].add(b)
        to1[b].add(a)
    dfs()
    
    
    m1=(n-1)//3+1
    m2=(n-2)//3+1
    m3=n//3
    
    if cntc[0]<cntc[1]:mnc=0
    else:mnc=1
    p1=list(range(1,n+1,3))
    p2=list(range(2,n+1,3))
    p3=list(range(3,n+1,3))
    ans=[-1]*n
    if cntc[mnc]<=m3:
        
        for u in range(n):
            if cc[u]==mnc:ans[u]=p3.pop()
            else:
                if p1:ans[u]=p1.pop()
                elif p2:ans[u]=p2.pop()
                else:ans[u]=p3.pop()
    elif cntc[1-mnc]>m1+m3:
        print(-1)
        exit()
    else:
        
        for u in range(n):
            if cc[u]==mnc:
                if p2:ans[u]=p2.pop()
                else:ans[u]=p3.pop()
            else:
                if p1:ans[u]=p1.pop()
                else:ans[u]=p3.pop()
    print(*ans)

main()