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):
n=int(input())
ki=[[] for _ in range(n)]

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

odd=[-1]*n
odd[0]=0
todo=[0]
while todo:
    v=todo.pop()
    for nv in ki[v]:
        if odd[nv]==-1:
            odd[nv]=abs(odd[v]-1)
            todo.append(nv)
from collections import Counter
co=Counter(odd)
ans=[0]*n
if co[1]<=n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==1 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1

elif co[0]<=n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==0 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1
else:
    cnt1=1
    cnt2=1
    cnt3=1
    for i in range(n):
        if odd[i]==1:
            if 3*cnt1-2<=n:
                ans[i]=3*cnt1-2
                cnt1+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
        else:
            if 3*cnt2-1<=n:
                ans[i]=3*cnt2-1
                cnt2+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
print(*ans,sep=' ')

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

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

    while not_yet:
        value = not_yet.popleft()
        for v in tree[value]:
            if already[v]:
                continue
            already[v] = True
            dist[v] = (dist[value] + 1) % 2
            not_yet.append(v)
    
    zero = dist.count(0)
    one = dist.count(1)

    ans = [0]*n
    already = [False]*n
    if zero >= one:
        if one <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 1:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 0:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1
    else:
        if zero <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 0:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 1:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1

    print(*ans)

            


    
if __name__ == "__main__":
    main()

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

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

    while not_yet:
        value = not_yet.popleft()
        for v in tree[value]:
            if already[v]:
                continue
            already[v] = True
            dist[v] = (dist[value] + 1) % 2
            not_yet.append(v)
    
    zero = dist.count(0)
    one = dist.count(1)

    ans = [0]*n
    already = [False]*n
    if zero >= one:
        if one <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 1:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 0:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1
    else:
        if zero <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 0:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 1:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1

    print(*ans)

            



    
if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
dist=[-1]*n
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)

from collections import deque
queue=deque([[0,i] for i in G[0]])
dist[0]=0
while queue:
    now,to=queue.pop()
    
    if dist[to]!=-1:continue
    dist[to]=1-dist[now]
    for i in G[to]:
        queue.appendleft([to,i])


q=sum(dist)
LAST=[0]*n
if n/3 <= q and n/3 <= n-q:
    
    A=[i for i in range(1,n+1,3)] + [0]*n
    

    B=[i for i in range(2,n+1,3)] + [0]*n


    now1=0
    now2=0
    for i in range(n):
        if dist[i]:
            LAST[i]=B[now2]
            now2+=1
        else:
            LAST[i]=A[now1]
            now1+=1
    w=3
    for i in range(n):
      if LAST[i]==0:
        LAST[i]=w
        w+=3
    print(*LAST)
            
elif n/3 >q:
    w=3
    for i in range(n):
        if dist[i]:
            LAST[i]=w
            w+=3
    A=[i for i in range(w,n+1,3)]+[i for i in range(1,n+1) if i%3!=0]
    now=0
    for i in range(n):
        if LAST[i]==0:
            LAST[i]=A[now]
            now+=1
    print(*LAST)
else:
    w=3
    for i in range(n):
        if dist[i]==0:
            LAST[i]=w
            w+=3
    A=[i for i in range(w,n+1,3)]+[i for i in range(1,n+1) if i%3!=0]
    now=0
    for i in range(n):
        if LAST[i]==0:
            LAST[i]=A[now]
            now+=1
    print(*LAST)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)

def is_bip(ns):
    start = 0
    q = [start]
    cs = [None]*n
    cs[start] = 1
    while q:
        u = q.pop()
        c = cs[u]
        cc = int(not c)
        for v in ns[u]:
            if cs[v] is None:
                cs[v] = cc
                q.append(v)
            elif cs[v]==c:
                return False, None
    return True, cs
_, cs = is_bip(ns)
v1, v0 = 0, 0
for num in cs:
    if num==0:
        v0 += 1
    else:
        v1 += 1
num0 = [i for i in range(1,n+1) if i%3==0]
num1 = [i for i in range(1,n+1) if i%3==1]
num2 = [i for i in range(1,n+1) if i%3==2]
if v0<=len(num0) or v1<=len(num0):
    if v0<=len(num0):
        val = 0
    else:
        val = 1
    for i in range(n):
        if cs[i]==val:
            cs[i] = num0.pop()
        else:
            if num1:
                cs[i] = num1.pop()
            elif num2:
                cs[i] = num2.pop()
            else:
                cs[i] = num0.pop()
else:
    if v0<=v1:
        val = 0
    else:
        val = 1
    for i in range(n):
        if cs[i]==val:
            if num1:
                cs[i] = num1.pop()
            else:
                cs[i] = num0.pop()
        else:
            if num2:
                cs[i] = num2.pop()
            else:
                cs[i] = num0.pop()
write(" ".join(map(str, cs)))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N=int(input())

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


def dfs(u,par,depth):
  dist_list[u]=depth
  for v in tree[u]:
    if v!=par:
      dfs(v,u,depth+1)
  
dist_list=[-1]*(N+1)
dfs(1,0,0)


num_even=num_odd=0
for i in range(1,N+1):
  if dist_list[i]%2==0:
    num_even+=1
  else:
    num_odd+=1


num_3m0=3
num_3m1=1
num_3m2=2
answer_list=[0]*(N+1)
if num_even<=N//3:
  for i in range(1,N+1):
    if dist_list[i]%2==0:
      answer_list[i]=num_3m0
      num_3m0+=3
    else:
      if num_3m1<=N:
        answer_list[i]=num_3m1
        num_3m1+=3
      elif num_3m2<=N:
        answer_list[i]=num_3m2
        num_3m2+=3
      else:
        answer_list[i]=num_3m0
        num_3m0+=3
elif num_odd<=N//3:
  for i in range(1,N+1):
    if dist_list[i]%2==1:
      answer_list[i]=num_3m0
      num_3m0+=3
    else:
      if num_3m1<=N:
        answer_list[i]=num_3m1
        num_3m1+=3
      elif num_3m2<=N:
        answer_list[i]=num_3m2
        num_3m2+=3
      else:
        answer_list[i]=num_3m0
        num_3m0+=3
else:
  for i in range(1,N+1):
    if dist_list[i]%2==0:
      if num_3m1<=N:
        answer_list[i]=num_3m1
        num_3m1+=3
      else:
        answer_list[i]=num_3m0
        num_3m0+=3
    else:
      if num_3m2<=N:
        answer_list[i]=num_3m2
        num_3m2+=3
      else:
        answer_list[i]=num_3m0
        num_3m0+=3
        
print(*answer_list[1:])

Solution (Python):
import collections
import sys
sys.setrecursionlimit(2*10**5)
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))

i0, i1 = 0, 1
if c[0] > c[1]:
    i0, i1 = 1, 0

ans = [None] * (N + 1)
if c[i0] <= len(cand3):
    for i in range(1, N + 1):
        if color[i]==i0:
            ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand2:
                ans[i] = cand2.pop()
            elif cand3:
                ans[i] = cand3.pop()
else:
    for i in range(1, N + 1):
        if color[i] == i0:
            if cand2:
                ans[i] = cand2.pop()
            elif cand3:
                ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand3:
                ans[i] = cand3.pop()
print(*ans[1:])

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

def bfs():
    color = [0]*N
    color[0] = 1
    q = deque([0])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
    
    return color

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)

n = [0, 0, 0]

for i in range(1, N+1):
    n[i%3] += 1
    
color = bfs()
b = color.count(1)

if b>N-b:
    for i in range(N):
        color[i] *= -1
        
ans = [-1]*N

if min(b, N-b)<=n[0]:
    q = deque([i for i in range(1, N+1) if i%3==0]+[i for i in range(1, N+1) if i%3!=0])
else:
    q = deque([i for i in range(1, N+1) if i%3==1]+[i for i in range(1, N+1) if i%3==0]+[i for i in range(1, N+1) if i%3==2])

for i in range(N):
    if color[i]==1:
        ans[i] = q.popleft()
        
for i in range(N):
    if color[i]==-1:
        ans[i] = q.popleft()

print(*ans)

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

N = int(input())

tree = [[] for _ in range(N)]
bip = [None for _ in range(N)]

for _ in range(N - 1):
    u, v = map(int, input().split())
    tree[u - 1].append(v - 1)
    tree[v - 1].append(u - 1)

stack = [0]
bip[0] = 0

while stack:
    node = stack.pop()
    for adj in tree[node]:
        if bip[adj] is not None:
            continue
        bip[adj] = not bip[node]
        stack.append(adj)

res = [None for _ in range(N)]

white = sum(bip)
black = N - white

p0 = []
p1 = []
p2 = []

for i in range(1, N + 1):
    if i % 3 == 0:
        p0.append(i)

for i in range(1, N + 1):
    if i % 3 == 1:
        p1.append(i)

for i in range(1, N + 1):
    if i % 3 == 2:
        p2.append(i)

if white <= N // 3:
    p = p0 + p1 + p2
    cnt = 0
    for i in range(N):
        if bip[i]:
            res[i] = p[cnt]
            cnt += 1
    for i in range(N):
        if not bip[i]:
            res[i] = p[cnt]
            cnt += 1
    print(*res)

elif black <= N // 3:
    p = p0 + p1 + p2
    cnt = 0
    for i in range(N):
        if not bip[i]:
            res[i] = p[cnt]
            cnt += 1
    for i in range(N):
        if bip[i]:
            res[i] = p[cnt]
            cnt += 1
    print(*res)

else:
    p = p1 + p0 + p2
    cnt = 0
    for i in range(N):
        if not bip[i]:
            res[i] = p[cnt]
            cnt += 1
    for i in range(N):
        if bip[i]:
            res[i] = p[cnt]
            cnt += 1
    print(*res)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

a = [1]
b = []
s = [1]
vis = [0] * (N + 1)
table = [-1] * (N + 1)
table[1] = 1
vis[1] = 1
while len(s):
  x = s.pop()
  for y in e[x]:
    if vis[y]: continue
    vis[y] = 1
    table[y] = table[x] ^ 1
    if table[y]: a.append(y)
    else: b.append(y)
    s.append(y)
if len(a) > len(b): a, b = b, a
res = [0] * (N + 1)
if len(a) <= N // 3:
  ss = set([x for x in range(1, N + 1)])
  x = 3
  for y in a:
    res[y] = x
    ss.discard(x)
    x += 3
  ss = list(ss)
  for i in range(1, N + 1):
    if res[i]: continue
    res[i] = ss.pop()
  print(*res[1: ])
else:
  ss = set([x for x in range(1, N + 1)])
  x = 2
  for y in a:
    res[y] = x
    ss.discard(x)
    x += 3
    if x > N: break
  x = 3
  for y in a:
    if res[y]: continue
    res[y] = x
    ss.discard(x)
    x += 3
  ss = list(ss)
  for i in range(1, N + 1):
    if res[i]: continue
    res[i] = ss.pop()
  print(*res[1: ])

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

rb = [-1]*n
rb[0] = 1
count1 = 1
count2 = 0
rb_m = [[0]]
for i in rb_m:
    n_rb = []
    for j in i:
        x = rb[j]
        for k in ab[j]:
            if(rb[k] != -1):
                continue
            if(x == 1):
                rb[k] = 2
                count2 += 1
            elif(x == 2):
                rb[k] = 1
                count1 += 1
            n_rb.append(k)
    set(n_rb)
    if(n_rb == []):
        break
    else:
        rb_m.append(n_rb)

ans = [0 for i in range(n)]
if(count1 > n//3 and count2 > n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 1 and ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(rb[i] == 2 and ne2 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
elif(count2 >= 2*n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 1):
            ans[i] = ne3
            ne3 += 3
        elif(ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(ne2 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
elif(count1 >= 2*n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 2):
            ans[i] = ne3
            ne3 += 3
        elif(ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(ne2 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
print(*ans)

Solution (Python):
from collections import deque
n=int(input())
E=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  E[a].append(b)
  E[b].append(a)
D=deque([0])
V=[0]*n
V[0]=1
A=[0]*n
k=1
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(E[x])):
    if V[E[x][i]]==0:
      V[E[x][i]]=1
      D.append(E[x][i])
      A[E[x][i]]=A[x]^1
f=0
if n-sum(A)>sum(A):
  f=1
g=max(n-sum(A),sum(A))
a=(n+2)//3
b=n//3
if g>a+b:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==0:
    for i in range(n):
      if A[i]==0:
        Ans[i]=u
        u=u+3
      else:
        if s<=n:
          Ans[i]=s
          s=s+3
        elif t<=n:
          Ans[i]=t
          t=t+3
        else:
          Ans[i]=u
          u=u+3
  else:
    for i in range(n):
      if A[i]==1:
        Ans[i]=u
        u=u+3
      else:
        if s<=n:
          Ans[i]=s
          s=s+3
        elif t<=n:
          Ans[i]=t
          t=t+3
        else:
          Ans[i]=u
          u=u+3
else:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==1:
    for i in range(n):
      if A[i]==0 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==0 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==1 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
  else:
    for i in range(n):
      if A[i]==1 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==1 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==0 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
print(*Ans)

Solution (Python):
from collections import deque
n=int(input())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
even=[]
odd=[]
ansl=[0]*n
nums=set([i for i in range(1,n+1)])
dist=[-1]*n
dist[0]=0
even.append(0)
D=deque([0])
while D:
    v=D.popleft()
    for i in graph[v]:
        if dist[i]!=-1:continue
        dist[i]=dist[v]+1
        D.append(i)
        if dist[i]%2:odd.append(i)
        else:even.append(i)
El=len(even)
Ol=len(odd)
if El <= Ol:
    if El <= n//3:
        for i in range(El):
            ansl[even[i]]=(i+1)*3
            nums.remove((i+1)*3)
        for i in range(Ol):
            ansl[odd[i]]=nums.pop()
    else:
        cnt=0
        while 3*cnt+2<=n:
            ansl[even[cnt]]=3*cnt+2
            ansl[odd[cnt]]=3*cnt+1
            nums.remove(3*cnt+2)
            nums.remove(3*cnt+1)
            cnt+=1
        for i in range(cnt,El):
            ansl[even[i]]=nums.pop()
        for i in range(cnt,Ol):
            ansl[odd[i]]=nums.pop()

if Ol < El:
    if Ol <= n//3:
        for i in range(Ol):
            ansl[odd[i]]=(i+1)*3
            nums.remove((i+1)*3)
        for i in range(El):
            ansl[even[i]]=nums.pop()
    else:
        cnt=0
        while 3*cnt+2<=n:
            ansl[odd[cnt]]=3*cnt+2
            ansl[even[cnt]]=3*cnt+1
            nums.remove(3*cnt+2)
            nums.remove(3*cnt+1)
            cnt+=1
        for i in range(cnt,Ol):
            ansl[odd[i]]=nums.pop()
        for i in range(cnt,El):
            ansl[even[i]]=nums.pop()
print(*ansl)

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

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

bigraph = [0] * n


def dfs(v, v_p, depth):
    bigraph[v] = depth % 2
    for v_next in graph[v]:
        if v_next == v_p:
            continue
        dfs(v_next, v, depth + 1)


dfs(0, -1, 1)
m1 = sum(bigraph)
m2 = n - m1

ans = [-1] * n
if m1 > n // 3 and m2 > n // 3:
    c1 = 1
    c2 = 2
    for i in range(n):
        if bigraph[i] == 0 and c1 <= n:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 1 and c2 <= n:
            ans[i] = c2
            c2 += 3
    c3 = 3
    for i in range(n):
        if ans[i] == -1:
            ans[i] = c3
            c3 += 3
elif m1 > m2:
    
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 0:
            
            ans[i] = c3
            c3 += 3
    for i in range(n):
        if ans[i] == -1:
            if c1 <= n:
                ans[i] = c1
                c1 += 3
            elif c2 <= n:
                ans[i] = c2
                c2 += 3
            else:
                ans[i] = c3
                c3 += 3
else:  
    
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 1:
            
            ans[i] = c3
            c3 += 3
    for i in range(n):
        if ans[i] == -1:
            if c1 <= n:
                ans[i] = c1
                c1 += 3
            elif c2 <= n:
                ans[i] = c2
                c2 += 3
            else:
                ans[i] = c3
                c3 += 3

print(*ans)

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

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)
mod_0 = []
mod_1 = []
mod_2 = []
for i in range(1, n + 1):
    if i % 3 == 0:
        mod_0.append(i)
    elif i % 3 == 1:
        mod_1.append(i)
    else:
        mod_2.append(i)
ans = [-1]*n
from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0 
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

d = bfs(0)

cnt = [[] for _ in range(2)]

for i in range(n):
    if d[i] % 2 == 0:
        cnt[0].append(i + 1)
    elif d[i] % 2 == 1:
        cnt[1].append(i + 1)

cnt = sorted(cnt, key=lambda x: len(x))

if len(mod_0) >= len(cnt[0]):
    for i in range(len(cnt[0])):
        ans[cnt[0][i] - 1] = mod_0.pop()
    for i in range(len(cnt[1])):
        if mod_0:
            ans[cnt[1][i] - 1] = mod_0.pop()
        elif mod_1:
            ans[cnt[1][i] - 1] = mod_1.pop()
        else:
            ans[cnt[1][i] - 1] = mod_2.pop()
    print(*ans)
    sys.exit()

for i in range(2):
    c = cnt[i]
    for j in range(len(c)):
        if mod_2 and i == 0:
            ans[cnt[i][j] - 1] = mod_2.pop()
        elif mod_1 and i == 1:
            ans[cnt[i][j] - 1] = mod_1.pop()
        elif mod_0:
            ans[cnt[i][j] - 1] = mod_0.pop()
        else:
            print(-1)
            sys.exit()
print(*ans)

Solution (Python):
from collections import deque
n=int(input())
E=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  E[a].append(b)
  E[b].append(a)
D=deque([0])
V=[0]*n
V[0]=1
A=[0]*n
k=1
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(E[x])):
    if V[E[x][i]]==0:
      V[E[x][i]]=1
      D.append(E[x][i])
      A[E[x][i]]=A[x]^1
f=0
if n-sum(A)>sum(A):
  f=1
g=max(n-sum(A),sum(A))
a=(n+2)//3
b=n//3
if g>a+b:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==0:
    for i in range(n):
      if A[i]==0:
        Ans[i]=u
        u=u+3
      else:
        if s<=n:
          Ans[i]=s
          s=s+3
        elif t<=n:
          Ans[i]=t
          t=t+3
        else:
          Ans[i]=u
          u=u+3
  else:
    for i in range(n):
      if A[i]==1:
        Ans[i]=u
        u=u+3
      else:
        if s<=n:
          Ans[i]=s
          s=s+3
        elif t<=n:
          Ans[i]=t
          t=t+3
        else:
          Ans[i]=u
          u=u+3
else:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==1:
    for i in range(n):
      if A[i]==0 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==0 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==1 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
  else:
    for i in range(n):
      if A[i]==1 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==1 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==0 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
print(*Ans)

Solution (Python):
from collections import deque
N = int(input())
G = [[] for _ in range(N + 1)]
dist = [-1 for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
zero = []
one = []
two = []
for i in range(1, N + 1):
    if i % 3 == 1:
        one.append(i)
    elif i % 3 == 2:
        two.append(i)
    else:
        zero.append(i)
q = deque([1])
dist[1] = 0

while q.__len__() != 0:
    s = q.popleft()
    for i in G[s]:
        if dist[i] == -1:
            q.append(i)
            dist[i] = (dist[s] + 1) % 2

red = 0
blue = 0

for i in range(1, N + 1):
    if dist[i] == 0:
        red += 1
    else:
        blue += 1
ans = []
if red > N / 3 and blue > N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0 and one.__len__() != 0:
            ans.append(one.pop())
        elif dist[i] == 1 and two.__len__() != 0:
            ans.append(two.pop())
        else:
            ans.append(zero.pop())
elif red <= N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

else:
    for i in range(1, N + 1):
        if dist[i] == 1:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

print(*ans)