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

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

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)

depth=[0]*N
def dfs(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            dfs(nv,v)

dfs(0,-1)

even=0
odd=0
for i in range(N):
    if depth[i]%2==0:
        even+=1
    else:
        odd+=1

ans=[0 for i in range(N)]

if N%3==0:
    if min(even,odd)>=N//3:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3>even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
elif N%3==2:
    if min(even,odd)>=N//3+1:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3+1>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3+1>even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
else:
    if even>=N//3+1 and odd>=N//3:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif even>=N//3 and odd>=N//3+1:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==1:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3>=even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)

Solution (Python):
g = {}
n=int(input())
m = [-1]*n
import sys
sys.setrecursionlimit(1000000000)
def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
ans=[0]*n
used=[0]*n
r=n//3
if 3*(r+1)<=n:
  r+=1
if zeros<=r:
  current=3
  for i in range(n):
    if m[i]==0:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==1:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
elif ones<=r:
  current=3
  for i in range(n):
    if m[i]==1:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==0:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
else:
  if zeros<ones:
    current=1
    for i in range(n):
      if m[i]==0:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
    counter=0
    for i in range(n):
      if m[i]==1:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
  else:
    current=1
    for i in range(n):
      if m[i]==1:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
      counter=0
    for i in range(n):
      if m[i]==0:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
for i in ans:
  print(i)

Solution (Python):
from collections import deque

def bfs():
    q = deque()
    q.append(1)
    dist = [-1] * (n + 1)
    dist[1] = 0
    while q:
        p = q.popleft()
        for i in G[p]:
            if dist[i] == -1:
                dist[i] = dist[p] + 1
                q.append(i)
    return dist

n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
dist = bfs()
c1, c2 = 0, 0
group1, group2 = [], []
for i in range(1, n + 1):
    if dist[i] % 2 == 1:
        c1 += 1
        group1.append(i)
    else:
        c2 += 1
        group2.append(i)
m = n // 3
ans = [0] * (n + 1)
if m >= min(c1, c2):
    l = [3 * i + 3 for i in range(m)] + [3 * (i // 2) + (i % 2) + 1 for i in range(n - m)]
    j = 0
    if c1 < c2:
        for i in group1:
            ans[i] = l[j]
            j += 1
        for i in group2:
            ans[i] = l[j]
            j += 1
    else:
        for i in group2:
            ans[i] = l[j]
            j += 1
        for i in group1:
            ans[i] = l[j]
            j += 1
else:
    j = 1
    for i in range(c1):
        if i <= (n - 1) // 3:
            ans[group1[i]] = 3 * i + 1
        else:
            ans[group1[i]] = 3 * j
            j += 1
    for i in range(c2):
        if i <= (n - 2) // 3:
            ans[group2[i]] = 3 * i + 2
        else:
            ans[group2[i]] = 3 * j
            j += 1
ans.pop(0)
print(*ans)

Solution (Python):
import collections
n = int(input())
one = collections.deque([1])
two = collections.deque([])
three = collections.deque([])
graph = [[] for _ in range(n)]

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    if i % 3 == 0: two.append(i + 2)
    elif i % 3 == 1: three.append(i + 2)
    else: one.append(i + 2)

que = collections.deque([0])
num = [0] * n
dist = [-1] * n
parity = [0] * 2
dist[0] = 0
flag = True
while len(que) != 0:
    i = que.popleft()
    parity[dist[i] % 2] += 1
    for j in graph[i]:
        if dist[j] != -1: continue
        dist[j] = dist[i] + 1
        que.append(j)

if parity[0] <= n // 3 or parity[1] <= n // 3:
    rem = 0 if parity[0] < parity[1] else 1
    for i, v in enumerate(dist):
        if v % 2 == rem:
            num[i] = str(three.popleft())
        else:
            if len(one) != 0: num[i] = str(one.popleft())
            elif len(two) != 0: num[i] = str(two.popleft())
            else: num[i] = str(three.popleft())
else:
    for i, v in enumerate(dist):
        if v % 2 == 0:
            if len(one) != 0: num[i] = str(one.popleft())
            elif len(three) != 0: num[i] = str(three.popleft())
            else:
                flag = False
                break
        else:
            if len(two) != 0: num[i] = str(two.popleft())
            elif len(three) != 0: num[i] = str(three.popleft())
            else:
                flag = False
                break

print(' '.join(num))

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

def bfs():
    q = deque([0])
    color = [0]*N
    color[0] = 1
    
    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)
    
cnt = [0]*3

for i in range(1, N+1):
    cnt[i%3] += 1

color = bfs()
m = color.count(1)
ans = [-1]*N

if m<=cnt[0]:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==1:
            ans[i] = c0
            c0 += 3
    
    for i in range(N):
        if color[i]==-1:
            if c0<=N:
                ans[i] = c0
                c0 += 3
            else:
                if c1<=N:
                    ans[i] = c1
                    c1 += 3
                else:
                    ans[i] = c2
                    c2 += 3
elif m>=N-cnt[0]:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==-1:
            ans[i] = c0
            c0 += 3
    
    for i in range(N):
        if color[i]==1:
            if c0<=N:
                ans[i] = c0
                c0 += 3
            else:
                if c1<=N:
                    ans[i] = c1
                    c1 += 3
                else:
                    ans[i] = c2
                    c2 += 3
else:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==1:
            if c1<=N:
                ans[i] = c1
                c1 += 3
            else:
                ans[i] = c0
                c0 += 3
        
    for i in range(N):
        if color[i]==-1:
            if c0<=N:
                ans[i] = c0
                c0 += 3
            else:
                ans[i] = c2
                c2 += 3

print(*ans)

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

    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    bipartite = [-1] * N
    bipartite[0] = 0

    dq = deque([0])
    while dq:
        v = dq.popleft()
        nb = bipartite[v] ^ 1
        for u in graph[v]:
            if ~bipartite[u]: continue
            bipartite[u] = nb
            dq.append(u)

    s0 = bipartite.count(0)
    s1 = N - s0

    it1 = iter(range(1, N + 1, 3))
    it2 = iter(range(2, N + 1, 3))
    it3 = iter(range(3, N + 1, 3))
    it123 = chain(it1, it2, it3)
    it13 = chain(it1, it3)
    it23 = chain(it2, it3)

    ans = [-1] * N
    K = N // 3
    if s0 <= K:
        for v in range(N):
            if bipartite[v] == 0:
                ans[v] = next(it3)
            else:
                ans[v] = next(it123)  
    elif s1 <= K:
        for v in range(N):
            if bipartite[v] == 1:
                ans[v] = next(it3)
            else:
                ans[v] = next(it123)
    else:
        for v in range(N):
            if bipartite[v] == 0:
                ans[v] = next(it13)
            else:
                ans[v] = next(it23)

    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
m = map(int,read().split())
AB = zip(m,m)
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
dist = [-1] * (N+1)
stack = [1]
dist[1] = 0
while stack:
    v = stack.pop()
    for w in graph[v]:
        if dist[w] == -1:
            dist[w] = dist[v] + 1
            stack.append(w)
 
ev = [i for i,x in enumerate(dist) if x % 2 == 0 and i > 0]
od = [i for i,x in enumerate(dist) if x % 2 == 1 and i > 0]
 
def make_perm(N, ev, od, x0, x1, x2, y0, y1, y2):
    assert len(ev) == x0 + x1 + x2
    assert len(od) == y0 + y1 + y2
    P = [0] * (N+1)
    for i in ev:
        if x0:
            P[i] = (x0 + y0) * 3
            x0 -= 1
            continue
        if x1:
            P[i] = (x1 + y1) * 3 - 2
            x1 -= 1
            continue
        if x2:
            P[i] = (x2 + y2) * 3 - 1
            x2 -= 1
            continue
    for i in od:
        if y0:
            P[i] = (x0 + y0) * 3
            y0 -= 1
            continue
        if y1:
            P[i] = (x1 + y1) * 3 - 2
            y1 -= 1
            continue
        if y2:
            P[i] = (x2 + y2) * 3 - 1
            y2 -= 1
            continue
    return P[1:]
 
def solve(N, ev, od):
    x0 = N // 3
    x1 = (N+2) // 3
    x2 = (N+1) // 3
    perm = [0] * (N+1)
    LE = len(ev)
    LO = len(od)
    if LE <= x0:
        return make_perm(N, ev, od, LE, 0, 0, x0-LE, x1, x2)
    if LO <= x0:
        return make_perm(N, ev, od, x0-LO, x1, x2, LO, 0, 0)
    if LE == x1:
        return make_perm(N, ev, od, 0, x1, 0, x0, 0, x2)
    if LO == x1:
        return make_perm(N, ev, od, x0, 0, x2, 0, x1, 0)
    
    return make_perm(N, ev, od, LE-x1, x1, 0, LO-x2, 0, x2)
 
P = solve(N, ev, od)
print(' '.join(map(str, P)))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    return 
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if i % 3 == 0:
            if r:
                ans[r.pop()] = i
            elif b:
                ans[b.pop()] = i
print(*ans)

Solution (Python):


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

def run(cur, tr, dist, d=1, pre=-1, recur=1, save_recur = []):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        if recur >500:
            dic_ = {'cur':node, 'tr': tr, 'dist': dist,
                              'd': (d + 1) % 2, 'pre': cur, 'recur': recur + 1}
            save_recur.append(dic_)
            return None
        run(node, tr, dist, (d+1)%2, pre=cur, recur=recur+1, save_recur=save_recur)
    return None

if __name__ == '__main__':
    
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])

    dist = {0: [1], 1: []}
    save_rec = []
    run(1, tr, dist, save_recur=save_rec)

    while True:
        save_rec2 = save_rec
        save_rec = []
        for dict in save_rec2:
            run(dict['cur'], dict['tr'], dict['dist'], dict['d'],
                dict['pre'], dict['recur'],save_recur = save_rec)
        if save_rec == []:break


    perm = [0] * (N+1)
    rem1_max, rem2_max, rem0_max = int(N/3),int(N/3),int(N/3)
    if N % 3 == 1:
        rem1_max +=1
    if N % 3 == 2:
        rem1_max += 1
        rem2_max += 1
    if (len(dist[0]) <= N/3) | (len(dist[0]) >= 2*N/3):
        bool = int(len(dist[0]) <= N/3)
        h0 = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3*i for i in range(h0, rem0_max+1)] + [3*i+1 for i in range(0, rem1_max)] + [3*i+2 for i in range(0, rem2_max)]
        for k, val in zip(dist[bool], nums):
            perm[k] = val
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        h1 = 0
        h2 = 0
        idx = 0
        bool = int((len(dist[0]) > len(dist[1])))
        for alpha in range(n):
            even = dist[bool][idx]
            perm[even] = alpha * 3 + 1
            odd = dist[1-bool][idx]
            perm[odd] = alpha * 3 + 2
            idx += 1
        h0 = 1
        for k in dist[1-bool][idx:]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3 * i for i in range(h0, rem0_max+1)] + [3 * i + 1 for i in range(n, rem1_max)] + [3 * i + 2 for i in range(n, rem2_max)]

        for h, k in enumerate(dist[bool][idx:]):
            perm[k] = nums[h]
    print(" ".join(list(map(str, perm[1:]))))

Solution (Python):



def solve(*args: str) -> str:
    n = int(args[0])
    T = {i: set() for i in range(1, n+1)}
    for ab in map(str.split, args[1:]):
        a, b = map(int, ab)
        T[a].add(b)
        T[b].add(a)

    R = set()
    B = set()

    stack = [(1, 0)]
    while stack:
        i, d = stack.pop()
        if i in R or i in B:
            continue
        if d % 2:
            R.add(i)
        else:
            B.add(i)
        for j in T[i]:
            stack.append((j, d+1))

    R, B = (R, B) if len(R) < len(B) else (B, R)

    ret = [0]*(n+1)
    if len(R) <= n//3:
        for i in range(1, n+1):
            if i % 3:
                ret[B.pop()] = i
            else:
                ret[R.pop() if R else B.pop()] = i
    else:
        for i in range(1, n+1, 3):
            ret[R.pop()] = i
        for i in range(2, n+1, 3):
            ret[B.pop()] = i
        for i in range(3, n+1, 3):
            ret[R.pop() if R else B.pop()] = i

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[] for _ 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)

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in G[now] :
        if col[i] == -1 :
            col[i] = (col[now] + 1)%2
            stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
else :
    mods = deque(mod1 + mod0 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()

print(*ans)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    
    if k >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    
    if k >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed == False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def bfs(pt,s):
    n = len(pt)
    d = [-1]*n
    d[s] = 0
    q = [s]
    c = 1
    while q:
        q1 = []
        for v in q:
            for u in pt[v]:
                if d[u] == -1:
                    d[u] = c
                    q1.append(u)
        q = q1
        c += 1
    return d

N = I()
a,b = LIR(N-1,2)

if N%3 == 0:
    one_num,two_num,zero_num = N//3,N//3,N//3
elif N%3 == 1:
    one_num,two_num,zero_num = N//3+1,N//3,N//3
else:
    one_num,two_num,zero_num = N//3+1,N//3+1,N//3

pt = edges_to_pt(a,b,N)
d = bfs(pt,0)


odd = []
even = []
for i in range(N):
    if d[i]%2 == 0:
        even.append(i)
    else:
        odd.append(i)

max_ = max(len(even),len(odd))
min_ = min(len(even),len(odd))
if max_ == len(even):
    max_index = even
    min_index = odd
else:
    max_index = odd
    min_index = even

ans = [0]*N


if max_ >= one_num and min_ >= two_num:
    for i in range(one_num):
        ans[max_index[i]] = 1
    for i in range(two_num):
        ans[min_index[i]] = 2

else:
    for i in range(one_num):
        ans[max_index[i]] = 1
    for i in range(one_num,one_num+two_num):
        ans[max_index[i]] = 2

one_p = 0
two_p = 0
zero_p = 1
for i in range(N):
    if ans[i] == 1:
        ans[i] = 3*one_p+1
        one_p += 1
    elif ans[i] == 2:
        ans[i] = 3*two_p+2
        two_p += 1
    else:
        ans[i] = 3*zero_p
        zero_p += 1

print(*ans)

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


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))



X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]


ans = []
x12, x3 = X[0] + X[1], X[2]
if colors.count(0) <= N // 3:
    for color in colors:
        if color == 0:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

elif colors.count(1) <= N // 3:
    for color in colors:
        if color == 1:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

else:
    for color in colors:
        if X[color]:
            ans.append(X[color].pop())
        else:
            ans.append(X[2].pop())

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

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


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



group = [-1]*N
group[0] = False
def categorize2g(pi, i, g):
    for ci in Edges[i]:
        if ci == pi:
            continue
        group[ci] = not g
        categorize2g(i, ci, not g)

categorize2g(-1, 0, 0)


ans = [0]*N
mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]
gtnum = sum(group)
if gtnum <= N//3:
    dq = deque(mod1+mod2+mod0)
elif N-gtnum <= N//3:
    dq = deque(mod0+mod1+mod2)
else:
    dq = deque(mod1+mod0+mod2)

if len(ans) == N:
    for i, g in enumerate(group):
        if g:
            ans[i] = dq.pop()
        else:
            ans[i] = dq.popleft()



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