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 ** 7)
input = sys.stdin.readline
import numpy as np

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

class TREE(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]


depth = np.array(TREE(es).depth)

ans = [0]*n

zero = one = two = n // 3
if n % 3 == 1: one += 1
if n % 3 == 2:
    one+=1
    two+=1

num_odd = np.count_nonzero(depth %2 == 1)

if num_odd <= n/3:
    for i in range(n):
        if depth[i] % 2 == 1:
            if zero > 0:
                ans[i] = zero*3
                zero -= 1
        else:
            if two > 0:
                ans[i] = two*3 - 1
                two -= 1
            elif one > 0:
                ans[i] = one*3 - 2
                one -= 1
            elif zero > 0:
                ans[i] = zero*3
                zero -= 1
            else:
                break
    else:
        print(*ans, sep=' ')
        exit()

if num_odd >= n/3*2:
    for i in range(n):

        if depth[i] % 2 == 0:
            if zero > 0:
                ans[i] = zero*3
                zero -= 1
        else:
            if two > 0:
                ans[i] = two*3 - 1
                two -= 1
            elif one > 0:
                ans[i] = one*3 - 2
                one -= 1
            elif zero > 0:
                ans[i] = zero*3
                zero -= 1
            else:
                break
    else:
        print(*ans, sep=' ')
        exit()


for i in range(n):
    if depth[i] % 2 == 0:
        if one > 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
else:
    print(*ans, sep=' ')
    exit()

Solution (Python):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd


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

data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

lst=[0 for i in range(N+1)]
stack=deque([[1,0]])
visited=set([1])

while stack:
    a,m=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            stack.append([p,m+1])
            lst[p]=m+1


oddslst=[i for i in range(len(lst)) if i and not lst[i]%2]
evenlst=[i for i in range(len(lst)) if i and lst[i]%2]
lst=[0 for i in range(N+1)]
if N//3<len(oddslst) and N//3<len(evenlst):
    for i in range(1,N+1):
        if i%3==1:
            lst[oddslst.pop()]=i
        if i%3==2:
            lst[evenlst.pop()]=i
    oddslst+=evenlst
    for i in range(1,N+1):
        if i%3==0:
            lst[oddslst.pop()]=i
else:
    if len(evenlst)<len(oddslst):
        oddslst,evenlst=evenlst,oddslst
    for i in range(1,N+1):
        if i%3==0:
            if oddslst:
                lst[oddslst.pop()]=i
            else:
                lst[evenlst.pop()]=i
        else:
            lst[evenlst.pop()]=i

print(" ".join([str(i) for i in lst if i]))

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

Solution (Python):
import sys

sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def dfs(n, d):
    if depth[n] != -1:
        return
    depth[n] = d
    for nn in eAB[n]:
        dfs(nn, d + 1)
    return


N = int(input())
AB = [inpl() for i in range(N - 1)]

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

depth = [-1 for i in range(N)]

dfs(0, 0)

eo = [[], []]
for i in range(N):
    eo[depth[i] % 2].append(i)


ans = [-1 for i in range(N)]
if len(eo[0]) > N // 3 and len(eo[1]) > N // 3:
    for i in range(N // 3):
        ans[eo[0][i]] = 3 * i + 1
        ans[eo[1][i]] = 3 * i + 2
    t_0 = N // 3
    t_1 = N // 3
    if N % 3 > 0:
        ans[eo[0][N // 3]] = 3 * (N // 3) + 1
        t_0 += 1
    if N % 3 > 1:
        ans[eo[1][N // 3]] = 3 * (N // 3) + 2
        t_1 += 1
    
    for i, v in enumerate(eo[0][t_0:] + eo[1][t_1:]):
        ans[v] = 3 * (i + 1)
else:
    if len(eo[0]) <= N // 3:
        ni = 0
    else:
        ni = 1
    tmp = [True for i in range(N + 1)]
    for i in range(len(eo[ni])):
        ans[eo[ni][i]] = 3 * (i + 1)
        tmp[3 * (i + 1)] = False
    tmp = [i for i, t in enumerate(tmp) if t is True]
    j = 1
    for i in range(N):
        if ans[i] != -1:
            continue
        ans[i] = tmp[j]
        j += 1

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

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

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

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

Q=[1]
COLOR[1]=1

while Q:
    x=Q.pop()
    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=1-COLOR[x]
            Q.append(to)

A1=N//3
A2=N//3
A3=N//3

if N%3==1:
    A1+=1
elif N%3==2:
    A1+=1
    A2+=1

S1=COLOR.count(1)
S2=COLOR.count(0)


SA=A1+A3-A2

if abs(S1-S2)<=SA:
    ANS=[0]*(N+1)
    now1=1
    now2=2
    if S1<S2:
        for i in range(1,N+1):
            if COLOR[i]==1:
                ANS[i]=now2
                now2+=3
            else:
                ANS[i]=now1
                now1+=3

    else:
        for i in range(1,N+1):
            if COLOR[i]==0:
                ANS[i]=now2
                now2+=3
            else:
                ANS[i]=now1
                now1+=3

    now3=3
    for i in range(1,N+1):
        if ANS[i]>N:
            ANS[i]=now3
            now3+=3

    print(*ANS[1:])
    
else:
    ANS=[0]*(N+1)
    now1=1
    now2=2
    now3=3

    if S1<S2:
        for i in range(1,N+1):
            if COLOR[i]==1:
                ANS[i]=now3
                now3+=3
    else:
        for i in range(1,N+1):
            if COLOR[i]==0:
                ANS[i]=now3
                now3+=3

    for i in range(1,N+1):
        if ANS[i]==0:
            if now1<=N:
                ANS[i]=now1
                now1+=3
            elif now2<=N:
                ANS[i]=now2
                now2+=3
            else:
                ANS[i]=now3
                now3+=3

    print(*ANS[1:])

Solution (Python):
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    root = 0  
    d = [-1]*n  
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d = [i % 2+1 for i in d]
    d2 = [0]*n
    x = d.count(1)
    y = d.count(2)
    if x > n//3 and y > n//3:
        j1 = 1
        for i in range(n):
            if d[i] == 1:
                d2[i] = j1
                j1 += 3
                cnt += 1
        j2 = 2
        for i in range(n):
            if d[i] == 2:
                d2[i] = j2
                j2 += 3
        j3 = 3
        for i in range(n):
            if d2[i] > n:
                d2[i] = j3
                j3 += 3
    elif x <= n//3:
        j3 = 3
        for i in range(n):
            if d[i] == 1:
                d2[i] = j3
                j3 += 3
        j2 = 1
        for i in range(n):
            if d[i] == 2:
                d2[i] = j2
                if j2 % 3 == 2:
                    j2 += 2
                else:
                    j2 += 1
        for i in range(n):
            if d2[i] > n:
                d2[i] = j3
                j3 += 3
    else:
        j3 = 3
        for i in range(n):
            if d[i] == 2:
                d2[i] = j3
                j3 += 3
        j2 = 1
        for i in range(n):
            if d[i] == 1:
                d2[i] = j2
                if j2 % 3 == 2:
                    j2 += 2
                else:
                    j2 += 1
        for i in range(n):
            if d2[i] > n:
                d2[i] = j3
                j3 += 3
    print(*d2)


main()

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


def dfs(v, step):
    global node0, node1
    if step & 1:
        color[v] = 1
        node1 += 1
    else:
        color[v] = 0
        node0 += 1
    for nv in edge[v]:
        if color[nv] is None:
            dfs(nv, step + 1)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
color = [None] * N
node0 = node1 = 0
dfs(0, 0)

ans = [None] * N
num0 = N // 3
num1 = N // 3 + (N % 3 >= 1)
num2 = N // 3 + (N % 3 == 2)
if node0 > num0 and node1 > num0:
    cur = 0
    while num1 > 0:
        if color[cur] == 1:
            ans[cur] = 3 * num1 - 2
            num1 -= 1
        cur += 1
    cur = 0
    while num2 > 0:
        if color[cur] == 0:
            ans[cur] = 3 * num2 - 1
            num2 -= 1
        cur += 1
elif node0 <= num0:
    cur = 0
    while node0 > 0:
        if color[cur] == 0:
            ans[cur] = 3 * num0
            num0 -= 1
            node0 -= 1
        cur += 1
else:
    cur = 0
    while node1 > 0:
        if color[cur] == 1:
            ans[cur] = 3 * num0
            num0 -= 1
            node1 -= 1
        cur += 1

cur = 0
while num0 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num0
        num0 -= 1
    cur += 1
while num1 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num1 - 2
        num1 -= 1
    cur += 1
while num2 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num2 - 1
        num2 -= 1
    cur += 1


print(*ans)

Solution (Python):

"""
Writer:SPD_9X2

木を2色で塗り分ける(交互に)

mod3で、
赤/青
10/20
20/10
120/0
0/120s
の4通りの分け方を試せばよい

絶対OKな証明
入る場合→入れればよい
入らない場合→mod0は必ずmod1,mod2以下の数。
mod0を入れても空きがあるとまずいけど、差は1以下なのでその場合はmod1が必ず入る
→おわり

"""


import sys
from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis

N = int(input())

lis = [[] for i in range(N)]
for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

dis,plis = NC_Dij(lis,0)

use = [1,2,3]

flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3
    if nex > N:
        nex = use[2]
        use[2] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()

use = [2,1,3]
flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3
    if nex > N:
        nex = use[2]
        use[2] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()

use = [3,1,2]
flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3
    if nex > N and nex % 3 == 1:
        nex = use[2]
        use[2] += 3
    if nex > N and nex % 3 == 2:
        nex = use[0]
        use[0] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()


use = [1,3,2]
flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3

    if nex > N and nex % 3 == 1:
        nex = use[2]
        use[2] += 3
    if nex > N and nex % 3 == 2:
        nex = use[1]
        use[1] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()



print (-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()
inf = 10**9
dist = [inf for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dist[i] = dist[node]+1
            dfs(i)
dist[1] = 0
rem_1 = [i+1 for i in range(n) if (i+1) % 3 == 1]
rem_2 = [i+1 for i in range(n) if (i+1) % 3 == 2]
rem_0 = [i+1 for i in range(n) if (i+1) % 3 == 0]
index_0 = 0
index_1 = 0
index_2 = 0
dfs(1)
ans = []
count_even = 0
count_odd = 0
for i in range(1,len(dist)):
    if dist[i] % 2 == 0:
        count_even += 1
    else:
        count_odd += 1


if count_even > n/3 and count_odd > n/3:
    
    for i in range(1,len(dist)):
        if dist[i] % 2 == 1:
            if index_2 < len(rem_2):
                ans.append(rem_2[index_2])
                index_2 += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
        else:
            if index_1 < len(rem_1):
                ans.append(rem_1[index_1])
                index_1 += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
elif count_even <= n/3:
    
    
    li = rem_1 + rem_2
    index = 0
    for i in range(1,len(dist)):
        if dist[i] % 2 == 0:
            ans.append(rem_0[index_0])
            index_0 += 1
        else:
            if index < len(li):
                ans.append(li[index])
                index += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
else:
    
    
    li = rem_1 + rem_2
    index = 0
    for i in range(1,len(dist)):
        if dist[i] % 2 == 1:
            ans.append(rem_0[index_0])
            index_0 += 1
        else:
            if index < len(li):
                ans.append(li[index])
                index += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
for i in ans:
    print(i, end=" ")

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
n = int(readline())

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

colors = [0] * (n+1)
 
colors[1] = 1
 
todo = []
for to in g[1]:
    todo.append([to, -1])
 
while todo:
    node, color = todo.pop()
 
    if colors[node] != 0:
        continue
 
    colors[node] = color
    new_color = -color
    for to in g[node]:
        if colors[to] != 0:
            continue
        todo.append([to, new_color])
ans = [0]*(n+1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1,n+1):
    if i%3==1:
        t1.append(i)
    elif i%3==2:
        t2.append(i)
    else:
        t0.append(i)
black = 0
for i in colors[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if colors[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
elif black >= n-n//3:
    for i in range(1,n+1):
        if colors[i] == -1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if colors[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2
    dfs(y)

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)

if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)


f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Solution (Python):
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

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

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 1)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for j in [1, 2, 0]:
                if len(nums[j]) > 0:
                    ans[i] = nums[j].pop()
                    break

if cnts[0] <= n // 3:
    
    solve(0)
elif cnts[1] <= n // 3:
    
    solve(1)
else:
    
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()

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

Solution (Python):
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
v=[-1]*n
v[0]=0
q=deque([0])
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
z=0
for i in v:
    if i==0:
        z+=1
ans=[0]*n
if z<=n//3:
    j=3
    for i in range(n):
        if v[i]==0:
            ans[i]=j
            j+=3
    j=1
    for i in range(n):
        if ans[i]==0:
            ans[i]=j
            j+=1
            if j%3==0 and j//3<=z:
                j+=1
    print(*ans)
elif n-z<=n//3:
    j=3
    for i in range(n):
        if v[i]==1:
            ans[i]=j
            j+=3
    j=1
    for i in range(n):
        if ans[i]==0:
            ans[i]=j
            j+=1
            if j%3==0 and j//3<=n-z:
                j+=1
    print(*ans)
else:
    o=1
    t=2
    tt=3
    for i in range(n):
        if v[i]==0 and o<=n:
            ans[i]=o
            o+=3
        elif v[i]==0:
            ans[i]=tt
            tt+=3
        if v[i]==1 and t<=n:
            ans[i]=t
            t+=3
        elif v[i]==1:
            ans[i]=tt
            tt+=3
    print(*ans)

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


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

colors = [-1] * n

colors[0] = 0

todo = []
for to in edges[0]:
    todo.append([to, 1])

while todo:
    node, color = todo.pop()

    if colors[node] != -1:
        continue

    colors[node] = color
    new_color = 1 - color
    for to in edges[node]:
        if colors[to] != -1:
            continue
        todo.append([to, new_color])

red_count = sum(colors)  
blue_count = n - red_count  

ans = [0] * n

num3s = list(range(3, n+1, 3))
nums = [num for num in range(1, n+1) if num % 3 != 0]

if red_count <= n // 3:
    for node in range(n):
        if colors[node] == 1:
            ans[node] = num3s.pop()

        else:
            if nums:
                num = nums.pop()
            else:
                num = num3s.pop()
            ans[node] = num


elif blue_count <= n // 3:
    for node in range(n):
        if colors[node] == 0:
            ans[node] = num3s.pop()

        else:
            if nums:
                num = nums.pop()
            else:
                num = num3s.pop()
            ans[node] = num

else:
    num1s = list(range(1, n+1, 3))
    num2s = list(range(2, n+1, 3))

    for node in range(n):
        if colors[node] == 1:
            if num1s:
                num = num1s.pop()
            else:
                num = num3s.pop()
            ans[node] = num

        else:
            if num2s:
                num = num2s.pop()
            else:
                num = num3s.pop()
            ans[node] = num

print(*ans)

Solution (Python):
N = int(input())
data = [[] for i in range(N)]

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

stack = [0]
d = [-1] * N
d[0] = 0

while stack:
    x = stack.pop()
    for y in data[x]:
        if d[y] != -1:
            continue
        d[y] = d[x] + 1
        stack.append(y)

mod = [[],[]]
for i in range(N):
    mod[d[i]%2].append(i)

ans = [0]*N

p = 1
q = 2
r = 3
if len(mod[0]) > N//3 and len(mod[1]) > N//3:
    for k in mod[0]:
        if p <= N:
            ans[k] = p
            p += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[1]:
        if q <= N:
            ans[l] = q
            q += 3
        else:
            ans[l] = r
            r += 3
    
elif len(mod[0]) > N//3:
    for k in mod[0]:
        if p <= N:
            ans[k] = p
            p += 3
        elif q <= N:
            ans[k] = q
            q += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[1]:
        ans[l] = r
        r += 3

else:
    for k in mod[1]:
        if p <= N:
            ans[k] = p
            p += 3
        elif q <= N:
            ans[k] = q
            q += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[0]:
        ans[l] = r
        r += 3

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

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

def main():
    n=int(input())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    Depth=[-1]*n
    Depth[0]=0
    q=deque()
    q.append(0)
    while q:
        fr=q.popleft()
        for to in Edges[fr]:
            if Depth[to]==-1:
                Depth[to]=Depth[fr]+1
                q.append(to)
    Group=[[] for _ in range(2)]
    for i in range(n):
        Group[Depth[i]%2].append(i)
    l_even,l_odd=len(Group[0]),len(Group[1])
    Ans=[0]*n
    Used=[False]*(n+1)
    if l_even<=l_odd:
        if l_even<=n//3:
            tmp_3=3;tmp_others=1
            for i in Group[0]:
                Ans[i]=tmp_3
                Used[tmp_3]=True
                tmp_3+=3
            for i in Group[1]:
                while Used[tmp_others]:
                    tmp_others+=1
                Ans[i]=tmp_others
                Used[tmp_others]=True
            return Ans
    else:
        if l_odd<=n//3:
            tmp_3=3;tmp_others=1
            for i in Group[1]:
                Ans[i]=tmp_3
                Used[tmp_3]=True
                tmp_3+=3
            for i in Group[0]:
                while Used[tmp_others]:
                    tmp_others+=1
                Ans[i]=tmp_others
                Used[tmp_others]=True
            return Ans
    tmp_even=1;tmp_odd=2;tmp_others=3
    for i in Group[0]:
        if tmp_even<=n:
            Ans[i]=tmp_even
            tmp_even+=3
        else:
            Ans[i]=tmp_others
            tmp_others+=3
    for i in Group[1]:
        if tmp_odd<=n:
            Ans[i]=tmp_odd
            tmp_odd+=3
        else:
            Ans[i]=tmp_others
            tmp_others+=3
    return Ans
    
if __name__=='__main__':
    Ans=main()
    print(*Ans)

Solution (Python):
from collections import deque


def solve(n, ab_list):
    g = [[] for _ in range(n + 1)]
    for a, b in ab_list:
        g[a].append(b)
        g[b].append(a)
    
    d_list = [-1] * (n + 1)
    d_list[1] = 0
    queue = deque([1])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if d_list[q] == -1:
                d_list[q] = d_list[p] + 1
                queue.append(q)
    
    cnt_2 = [0] * 6
    for i in range(1, n + 1):
        cnt_2[d_list[i] % 2] += 1

    if cnt_2[0] <= cnt_2[1]:
        min_01 = 0
    else:
        min_01 = 1

    min_sum = cnt_2[min_01]
    if min_sum <= n // 3:
        res_list = [0] * n
        list_3 = [3 * (k + 1) for k in range(min_sum)]
        list_other = [k for k in range(1, n + 1) if k % 3 != 0] + [3 * (k + 1) for k in range(min_sum, n // 3)]
        for i in range(1, n + 1):
            if d_list[i] % 2 == min_01:
                res_list[i - 1] = list_3.pop()
            else:
                res_list[i - 1] = list_other.pop()
    else:
        res_list = [0] * n
        add_1 = min_sum - (n + 2) // 3
        list_1 = [k + 1 for k in range(n) if k % 3 == 0] + [3 * (k + 1) for k in range(add_1)]
        list_2 = [k + 1 for k in range(n) if k % 3 == 1] + [3 * (k + 1) for k in range(add_1, n // 3)]
        for i in range(1, n + 1):
            if d_list[i] % 2 == min_01:
                res_list[i - 1] = list_1.pop()
            else:
                res_list[i - 1] = list_2.pop()

    return " ".join([str(r) for r in res_list])


def main():
    n = int(input())
    ab_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, ab_list)
    print(res)


def test():
    
    assert solve(5, [[1, 2], [1, 3], [3, 4], [3, 5]]) == "3 4 1 5 2"


if __name__ == "__main__":
    
    main()