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())


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

even_v = []
odd_v = []

is_reached = [False] * (N+1)
q = queue.Queue()

q.put([1, 0])


while not q.empty():
    v, d = q.get()
    if is_reached[v]:
        continue
    is_reached[v] = True
    
    if d%2 == 0:
        even_v.append(v)
    else:
        odd_v.append(v)

    for tv in e[v]:
        q.put([tv, d+1])


r1 = list(range(1, N+1, 3))
r2 = list(range(2, N+1, 3))
r3 = list(range(3, N+1, 3))

p = [0] * N
if len(even_v) <= len(r3):
    
    for v in even_v:
        p[v-1] = r3.pop()
elif len(odd_v) <= len(r3):
    
    for v in odd_v:
        p[v-1] = r3.pop()
else:
    
    for v in even_v:
        if not r1:
            break
        p[v-1] = r1.pop()
    
    for v in odd_v:
        if not r2:
            break
        p[v-1] = r2.pop()


rv = []
rv.extend(r1)
rv.extend(r2)
rv.extend(r3)
for i, _ in enumerate(p):
    if p[i] == 0:
        p[i] = rv.pop()

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

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

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



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

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



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

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

dfs(1,-1,1)

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


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    

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

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

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

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

    print(*ans[1:])

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]


class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self, rank, parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor is parent:
                continue
            neighbor.set_rank(rank=rank + 1, parent=self)


trees = {i: Tree(i) for i in range(1, N + 1)}

for a, b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
try:
    trees[1].set_rank(1, None)
except:
    print(-1)
    exit()

group0 = [node.v for node in trees.values() if node.rank % 2 == 0]
group1 = [node.v for node in trees.values() if node.rank % 2]
x = [set(), set(), set()]
for i in range(1, N + 1):
    x[i % 3].add(i)
if len(group1) < len(group0):
    group1, group0 = group0, group1
result = {}
if len(group0) <= len(x[0]):
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    y = x[0] | x[1] | x[2]
    while group1 and y:
        result[group1.pop()] = y.pop()
else:
    while x[2] and group0:
        result[group0.pop()] = x[2].pop()
    while x[1] and group1:
        result[group1.pop()] = x[1].pop()
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    while group1 and x[0]:
        result[group1.pop()] = x[0].pop()
    if group0 or group1:
        print(-1)
        exit()

print(' '.join(str(result[i]) for i in range(1, N + 1)))

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if len(even) <= n // 3:
    odd, even = even, odd
if len(odd) <= n // 3:
    r = r2 + r1 + r0
else:
    r = r1 + r0 + r2
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()

print(*ans)

Solution (Python):
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
v=[0]*N
x=[0]*N
for i,j in AB:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
import sys
sys.setrecursionlimit(10**9)
def dfs(p):
    y=1 if x[p]==2 else 2
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            x[n]=y
            dfs(n)
v[0]=x[0]=1
dfs(0)
def f(x,a,b):
    p,q,r=0,0,1
    for i in range(N):
        if x[i]==a and p*3+1<=N:
            x[i]=p*3+1
            p+=1
        elif x[i]==b and q*3+2<=N:
            x[i]=q*3+2
            q+=1
        else:
            x[i]=r*3
            r+=1
if x.count(1)<=N//3:
    f(x,2,2)
elif x.count(2)<=N//3:
    f(x,1,1)
else:
    f(x,1,2)
print(*x)

Solution (Python):
import queue

N = int(input())

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

even_v = []
odd_v = []

is_reached = [False] * (N+1)
q = queue.Queue()

q.put([1, 0])


while not q.empty():
    v, d = q.get()
    if is_reached[v]:
        continue
    is_reached[v] = True
    
    if d%2 == 0:
        even_v.append(v)
    else:
        odd_v.append(v)

    for tv in e[v]:
        q.put([tv, d+1])

r1 = list(range(1, N+1, 3))
r2 = list(range(2, N+1, 3))
r3 = list(range(3, N+1, 3))

ans = [0] * N
if len(even_v) <= len(r3):
    for v in even_v:
        ans[v-1] = r3.pop()
elif len(odd_v) <= len(r3):
    for v in odd_v:
        ans[v-1] = r3.pop()
else:
    for v in even_v:
        if not r1:
            break
        ans[v-1] = r1.pop()
    for v in odd_v:
        if not r2:
            break
        ans[v-1] = r2.pop()
rv = []
rv.extend(r1)
rv.extend(r2)
rv.extend(r3)
for i, p in enumerate(ans):
    if p == 0:
        ans[i] = rv.pop()

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

Solution (Python):
from collections import deque
N, *L = map(int, open(0).read().split())
E = [[] for i in range(N+1)]
for a,b  in zip(*[iter(L)]*2):
  E[a].append(b)
  E[b].append(a)
q = deque([1])
dist = [-1]*(N+1)
dist[1] = 0
dic = [[1],[]]
while q:
  u = q.popleft()
  for v in E[u]:
    if dist[v]==-1:
      dist[v] = dist[u]+1
      q.append(v)
      dic[dist[v]%2].append(v)

a = len(dic[0])
b = len(dic[1])

seq = set(range(1,N+1))
ver = set(range(1,N+1))
ans = [0]*(N+1)
if a>N//3 and b>N//3:
  for i in range(1,N+1,3):
    v = dic[1].pop()
    ans[v] = i
  q = 0
  for i in range(2,N+1,3):
    v = dic[0].pop()
    ans[v] = i
  m = 3
  while dic[0]:
    v = dic[0].pop()
    ans[v] = m
    m += 3
  while dic[1]:
    v = dic[1].pop()
    ans[v] = m
    m += 3
elif a<=N//3:
  seq = set(range(1,N+1))
  m = 3
  while dic[0]:
    v = dic[0].pop()
    ans[v] = m
    seq.remove(m)
    m += 3
  seq = list(seq)
  while dic[1]:
    v = dic[1].pop()
    ans[v] = seq.pop()
else:
  seq = set(range(1,N+1))
  m = 3
  while dic[1]:
    v = dic[1].pop()
    ans[v] = m
    seq.remove(m)
    m += 3
  seq = list(seq)
  while dic[0]:
    v = dic[0].pop()
    ans[v] = seq.pop()
print(*ans[1:])

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

from collections import defaultdict



def resolve():
    global N, neighbor_list, color_list, count_dict
    
    N = [int(x) for x in sys.stdin.readline().split()][0]  
    
    

    
    
    neighbor_list = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = sys.stdin.readline().split()
        a = int(a) - 1
        b = int(b) - 1
        neighbor_list[a].append(b)
        neighbor_list[b].append(a)

    logger.debug('{}'.format([]))

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

    count_dict = defaultdict(int)

    dfs(0, 0)

    q0_list = list(range(3, N + 1, 3))
    q1_list = list(range(1, N + 1, 3))
    q2_list = list(range(2, N + 1, 3))
    ret_list = [0 for _ in range(N)]
    if count_dict[0] > N // 3 and count_dict[1] > N // 3:
        i_q0 = i_q1 = i_q2 = 0
        for i, c in enumerate(color_list):
            if c == 0:
                if i_q1 < len(q1_list):
                    ret_list[i] = q1_list[i_q1]
                    i_q1 += 1
                else:
                    ret_list[i] = q0_list[i_q0]
                    i_q0 += 1
            else:
                if i_q2 < len(q2_list):
                    ret_list[i] = q2_list[i_q2]
                    i_q2 += 1
                else:
                    ret_list[i] = q0_list[i_q0]
                    i_q0 += 1
        print(' '.join([str(c) for c in ret_list]))
        return

    if count_dict[0] <= N // 3:
        i_q0 = i_q1 = i_q2 = 0
        for i, c in enumerate(color_list):
            if c == 0:
                ret_list[i] = q0_list[i_q0]
                i_q0 += 1

        for i, c in enumerate(color_list):
            if c == 1:
                if i_q0 < len(q0_list):
                    ret_list[i] = q0_list[i_q0]
                    i_q0 += 1
                elif i_q1 < len(q1_list):
                    ret_list[i] = q1_list[i_q1]
                    i_q1 += 1
                else:
                    ret_list[i] = q2_list[i_q2]
                    i_q2 += 1
        print(' '.join([str(c) for c in ret_list]))
        return

    if count_dict[1] <= N // 3:
        i_q0 = i_q1 = i_q2 = 0
        for i, c in enumerate(color_list):
            if c == 1:
                ret_list[i] = q0_list[i_q0]
                i_q0 += 1

        for i, c in enumerate(color_list):
            if c == 0:
                if i_q0 < len(q0_list):
                    ret_list[i] = q0_list[i_q0]
                    i_q0 += 1
                elif i_q1 < len(q1_list):
                    ret_list[i] = q1_list[i_q1]
                    i_q1 += 1
                else:
                    ret_list[i] = q2_list[i_q2]
                    i_q2 += 1
        print(' '.join([str(c) for c in ret_list]))
        return


def dfs(i, color):
    global N, neighbor_list, color_list, count_dict
    color_list[i] = color
    count_dict[color] += 1
    for i_next in neighbor_list[i]:
        if color_list[i_next] is None:
            dfs(i_next, not color)


if __name__ == "__main__":
    resolve()





import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
1 2
1 3
3 4
3 5"""
        output = """1 2 5 4 3"""
        self.assertIO(input, output)

Solution (Python):
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(a)
  
colors = [-1] * n


q = deque()

q.append((0, 0))
while q:
  v, pcol = q.popleft()
  
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
    for i in e[v]:
      if colors[i] == -1:
        q.append((i, col))



        
m = [deque([i for i in range(1, n + 1) if i % 3 == j]) for j in range(3)]



def opop(n, ne):
  if m[n]:
    p = m[n].pop()
  else:
    if n == 1 or n == 2:
      if m[ne]:
        p = m[ne].pop()
      else:
        p = m[0].pop()
    else:
      if m[1]:
        p = m[1].pop()
      else:
        p = m[2].pop()
  return p

ans = [0] * n

if sum(colors) <= len(m[0]):
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(0, 0)
    else:
      ans[itr] = opop(1, 2)
elif sum(colors) >= len(m[1]) + len(m[2]):
  for itr, i in enumerate(colors):
    if not i:
      ans[itr] = opop(0, 0)
    else:
      ans[itr] = opop(1, 2)
else:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(1, 0)
    else:
      ans[itr] = opop(2, 0)
print(*ans)

Solution (Python):
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(a)
  
colors = [-1] * n


q = deque()

q.append((0, 0))
while q:
  v, pcol = q.popleft()
  
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
    for i in e[v]:
      if colors[i] == -1:
        q.append((i, col))



        
m = [deque([i for i in range(1, n + 1) if i % 3 == j]) for j in range(3)]



def opop(n, ne):
  if m[n]:
    p = m[n].pop()
  else:
    if n == 1 or n == 2:
      if m[ne]:
        p = m[ne].pop()
      else:
        p = m[0].pop()
    else:
      if m[1]:
        p = m[1].pop()
      else:
        p = m[2].pop()
  return p

ans = [0] * n

if sum(colors) <= len(m[0]):
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(0, 0)
    else:
      ans[itr] = opop(1, 2)
elif sum(colors) >= len(m[1]) + len(m[2]):
  for itr, i in enumerate(colors):
    if not i:
      ans[itr] = opop(0, 0)
    else:
      ans[itr] = opop(1, 2)
else:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(1, 0)
    else:
      ans[itr] = opop(2, 0)
print(*ans)

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

num = [-1]*N
q = deque()
q.append((0, 0))
num[0] = 0
while q:
    temp = q.popleft()
    u = temp[0]
    n = temp[1]
    for v in E[u]:
        if num[v] >= 0:
            continue
        num[v] = (n+1)%2
        q.append((v, (n+1)%2))

ans = [0]*N
if sum(num) <= N//3 or N-sum(num) <= N//3:
    f = 1
    if N-sum(num) <= N//3:
        f = 0
    s = 1
    t = 3
    for i in range(N):
        if num[i] == f:
            ans[i] = t
            t += 3
    for i in range(N):
        if ans[i] == 0:
            ans[i] = s
            s += 1
            if s%3 == 0 and s < t:
                s += 1
else:
    s = 1
    t = 2
    u = 3
    for i in range(N):
        if num[i] == 0 and s <= N:
            ans[i] = s
            s += 3
        elif num[i] == 1 and t <= N:
            ans[i] = t
            t += 3
        else:
            ans[i] = u
            u += 3

print(*ans)

Solution (Python):
from collections import deque

import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

dist = [10**10] * N
que = deque([(0, 0)])
while que:
    now, d = que.popleft()

    if dist[now] <= d:
        continue
    dist[now] = d

    for to in edges[now]:
        que.append((to, d + 1))

A = [i for i, d in enumerate(dist) if d % 2 == 0]
B = [i for i, d in enumerate(dist) if d % 2 == 1]

if len(A) > len(B):
    A, B = B, A

ans = [-1] * N
nums = set(range(1, N + 1))

if len(A) <= N // 3:
    mul = 1
    for i in A:
        ans[i] = 3 * mul
        nums.remove(3 * mul)
        mul += 1
    nums = list(nums)
    for i, n in zip(B, nums):
        ans[i] = n
else:
    mul = 1
    for c, i in enumerate(A):
        if c * 3 + 1 > N:
            ans[i] = mul * 3
            mul += 1
        else:
            ans[i] = c * 3 + 1
    for c, i in enumerate(B):
        if c * 3 + 2 > N:
            ans[i] = mul * 3
            mul += 1
        else:
            ans[i] = c * 3 + 2

print(*ans)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])
 
def bfs(n,g):
    dis = [-1 for _ in range(n)]
    que = deque([])
    que.append(0)
    dis[0] = 0
    ODD = []
    EVEN = [0]
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] != -1:
                continue
            dis[g[go][i]] = dis[go] + 1
            if dis[g[go][i]]%2 == 0:
                EVEN.append(g[go][i])
            else:
                ODD.append(g[go][i])
            que.append(g[go][i])
    return EVEN,ODD
 
def main():
    n = inp()
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = inpm()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    EVEN,ODD = bfs(n,g)
    ans = [0 for _ in range(n)]
    check = [1 for _ in range(n)]
    mod0 = deque()
    mod1 = deque()
    mod2 = deque()
    for i in range(1,n+1):
        if i%3 == 0:
            mod0.append(i)
        if i%3 == 1:
            mod1.append(i)
        if i%3 == 2:
            mod2.append(i)
    if len(ODD) <= n//3:
        x = 1
        while ODD:
            index = ODD.pop()
            ans[index] = 3*x
            check[3*x-1] = 0
            x += 1
        i = 0
        while EVEN:
            index = EVEN.pop()
            while not check[i]:
                i += 1
            ans[index] = i+1
            i += 1
        print(*ans)
        return
    if len(EVEN) <= n//3:
        x = 1
        while EVEN:
            index = EVEN.pop()
            ans[index] = 3*x
            check[3*x-1] = 0
            x += 1
        i = 0
        while ODD:
            index = ODD.pop()
            while not check[i]:
                i += 1
            ans[index] = i+1
            i += 1
        print(*ans)
        return
    if len(ODD) <= len(EVEN):
        while mod1:
            index = EVEN.pop()
            ans[index] = mod1.pop()
        while mod2:
            index = ODD.pop()
            ans[index] = mod2.pop()
    else:
        while mod1:
            index = ODD.pop()
            ans[index] = mod1.pop()
        while mod2:
            index = EVEN.pop()
            ans[index] = mod2.pop()
    while mod0:
        if EVEN:
            index = EVEN.pop()
        else:
            index = ODD.pop()
        ans[index] = mod0.pop()
    print(*ans)
 
if __name__ == "__main__":
    main()

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

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

edges = {}
for i in range(1,n+1):
    edges[i] = set()

for tmp in ab:
    a,b = tmp
    edges[a].add(b)
    edges[b].add(a)

group = [[],[]]
g_flag = 0
next = {1}
while(len(next) > 0):
    tmp = list(next)
    next = set()
    for i in tmp:
        group[g_flag].append(i)
        for j in edges[i]:
            next.add(j)
            edges[j].remove(i)
    g_flag = 1- g_flag

even_n = len(group[0])
odd_n = len(group[1])

ans = [0] * (n+1)
if(even_n > n//3)&(odd_n > n//3):
    g1 = group[0][ : (n+2)//3]
    g2 = group[1][ : (n+1)//3]
    g0 = group[0][(n+2)//3 :] + group[1][(n+1)//3 :]
elif(even_n <= n//3):
    g0 = group[0]+ group[1][: n//3 - even_n]
    g1 = group[1][n//3 - even_n : (n//3 - even_n) + (n+2)//3]
    g2 = group[1][(n//3 - even_n) + (n+2)//3 :]
else:
    g0 = group[1] + group[0][: n//3 - odd_n]
    g1 = group[0][n//3 - odd_n : (n//3 - odd_n) + (n+2)//3]
    g2 = group[0][(n//3 - odd_n) + (n+2)//3 :]






for i in range((n+2)//3):
    ans[g1[i]] = i*3 + 1
for i in range((n+1)//3):
    ans[g2[i]] = i*3 + 2
for i,val in enumerate(g0):
    ans[val] = (i+1) * 3

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

Solution (Python):
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache




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)

color=[-1 for i in range(n)]
color[0]=0
def coloring(x):
    for i in G[x]:
        if color[i] != -1:continue
        color[i]=1-color[x]
        coloring(i)
coloring(0)
A=[];B=[]
ans=[0 for i in range(n)]
for i in range(n):
    if color[i]==0:A.append(i)
    else:B.append(i)


if 1:
    if len(A)>len(B):
        A,B=B,A
    
    if len(A)<=n//3:
      qq=deque([i for i in range(3,n+1,3)]+[i for i in range(1,n+1,3)]+[i for i in range(2,n+1,3)])
      for i in A:
          ans[i]=qq.popleft()
      for i in B:
          ans[i]=qq.popleft()
      print(*ans)
      exit()
    
    else:
      qq=deque([i for i in range(1,n+1,3)]+[i for i in range(3,n+1,3)]+[i for i in range(2,n+1,3)])
      for i in A:
          ans[i]=qq.popleft()
      for i in B:
          ans[i]=qq.popleft()
      print(*ans)
      exit()

Solution (Python):
n,*L=map(int,open(0).read().split())
g=[[]for _ in range(n)]
for a,b in zip(*[iter(L)]*2):
	g[a-1].append(b-1)
	g[b-1].append(a-1)
b=[-1]*n
b[0]=0
q=__import__("collections").deque([0])
while q:
	c=q.pop()
	for x in g[c]:
		if b[x]<0:b[x]=1-b[c];q.append(x)
lab=[-1]*n
Z=[i for i,x in enumerate(b) if x==0]
O=[i for i,x in enumerate(b) if x]
z=len(Z)
if z<=n//3 or n-z<=n//3:
	(L,H)=(Z,O) if z<=n//3 else (O,Z)
	a,b=1,3
	for i in L:lab[i]=b;b+=3
	for i in H:
		if b<=n:lab[i]=b;b+=3
		else:lab[i]=a;a+=1 if a%3==1 else 2
else:
	a,b,c=1,2,3
	for i in Z:
		if a<=n:lab[i]=a;a+=3
		else:lab[i]=c;c+=3
	for i in O:
		if b<=n:lab[i]=b;b+=3
		else:lab[i]=c;c+=3
print(*lab)

Solution (Python):
import sys
from collections import deque, Counter

n = int(input())
es = [[] for _ in range(n + 1)]

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

depth = [-1 for _ in range(n + 1)]
dq = deque([1])
depth[1] = 0

while dq:
	v = dq.pop()
	for e in es[v]:
		if depth[e] != -1:
			continue
		depth[e] = depth[v] + 1
		dq.append(e)

ans = [-1 for _ in range(n + 1)]	
cnt_dict = Counter([x % 2 for x in depth[1:]])

nums = [[i for i in range(1, n + 1) if i % 3 == 1], [i for i in range(1, n + 1) if i % 3 == 2], [i for i in range(1, n + 1) if i % 3 == 0]]
if cnt_dict[0] <= n // 3:
	for i in range(1, n + 1):
		if depth[i] % 2 == 0:
			ans[i] = nums[2].pop()
		else:
			if nums[0]:
				ans[i] = nums[0].pop()
			elif nums[1]:
				ans[i] = nums[1].pop()
			else:
				ans[i] = nums[2].pop()
elif cnt_dict[1] <= n // 3:
	for i in range(1, n + 1):
		if depth[i] % 2 == 1:
			ans[i] = nums[2].pop()
		else:
			if nums[0]:
				ans[i] = nums[0].pop()
			elif nums[1]:
				ans[i] = nums[1].pop()
			else:
				ans[i] = nums[2].pop()
else:
	for i in range(1, n + 1):
		if depth[i] % 2 == 0:
			if nums[0]:
				ans[i] = nums[0].pop()
			else:
				ans[i] = nums[2].pop()
		else:
			if nums[1]:
				ans[i] = nums[1].pop()
			else:
				ans[i] = nums[2].pop()

print(*ans[1:])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [-1]*n
    d[0] = 0
    q = deque([0])
    while q:
        x = q.popleft()
        nd = d[x]^1
        for y in v[x]:
            if d[y] < 0:
                d[y] = nd
                q.append(y)
    n1 = sum(d)
    n0 = len(d)-n1
    if n1 > n0:
        for i in range(n):
            d[i] ^= 1
        n0,n1 = n1,n0
    p = [(n+2)//3, (n+1)//3, n//3]
    k = [1,2,3]
    ans = [0]*n
    if n1 >= p[1]:
        for i in range(n):
            di = d[i]
            if not p[di]:
                di = 2
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    else:
        for i in range(n):
            di = d[i]
            if di == 1:
                di = 2
            while not p[di]:
                di += 1
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    print(*ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if n < 4:
        print(*range(1,n+1),sep = " ")
        return
    d = [-1]*n
    d[0] = 0
    q = deque([0])
    while q:
        x = q.popleft()
        nd = d[x]^1
        for y in v[x]:
            if d[y] < 0:
                d[y] = nd
                q.append(y)
    n1 = sum(d)
    n0 = len(d)-n1
    if n1 > n0:
        for i in range(n):
            d[i] ^= 1
        n0,n1 = n1,n0
    p = [(n+2)//3, (n+1)//3, n//3]
    k = [1,2,3]
    ans = [0]*n
    if n1 >= p[1]:
        for i in range(n):
            di = d[i]
            if not p[di]:
                di = 2
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    else:
        for i in range(n):
            di = d[i]
            if di == 1:
                di = 2
            while not p[di]:
                di += 1
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    print(*ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
n,*L=map(int,open(0).read().split())
g=[[]for _ in range(n)]
for a,b in zip(*[iter(L)]*2):
	g[a-1].append(b-1)
	g[b-1].append(a-1)
b=[-1]*n
b[0]=0
q=[0]
while q:
	c=q.pop()
	for x in g[c]:
		if b[x]<0:b[x]=1-b[c];q.append(x)
lab=[-1]*n
Z=[i for i,x in enumerate(b) if x==0]
O=[i for i,x in enumerate(b) if x]
z,o=len(Z),len(O)
if z<=n//3 or o<=n//3:
	(L,H)=(Z,O) if z<=n//3 else (O,Z)
	a,b=1,3
	for i in L:lab[i]=b;b+=3
	for i in H:
		if b<=n:lab[i]=b;b+=3
		else:lab[i]=a;a+=1 if a%3==1 else 2
else:
	a,b,c=1,2,3
	for i in Z:
		if a<=n:lab[i]=a;a+=3
		else:lab[i]=c;c+=3
	for i in O:
		if b<=n:lab[i]=b;b+=3
		else:lab[i]=c;c+=3
print(*lab)

Solution (Python):
n,*L=map(int,open(0).read().split())
g=[[]for _ in range(n)]
for a,b in zip(*[iter(L)]*2):
	g[a-1].append(b-1)
	g[b-1].append(a-1)
tr=[-1]*n
q=[0]
tr[0]=0
while q:
	cu=q.pop()
	for nx in g[cu]:
		if tr[nx]<0:
			tr[nx]=1-tr[cu]
			q.append(nx)
lab=[-1]*n
z,o=map(tr.count,(0,1))
if z<=n//3 or o<=n//3:
	f=0 if z<=n//3 else 1
	onetwo=1
	thr=3
	for i,x in enumerate(tr):
		if x==f:
			lab[i]=thr
			thr+=3
	for i,x in enumerate(tr):
		if x==1-f:
			if thr<=n:
				lab[i]=thr
				thr+=3
			else:
				lab[i]=onetwo
				onetwo+=1 if onetwo%3==1 else 2
else:
	one=1
	for i,x in enumerate(tr):
		if x==0:
			lab[i]=one
			one+=3
			if one>n:
				break
	two=2
	for i,x in enumerate(tr):
		if x==1:
			lab[i]=two
			two+=3
			if two>n:
				break
	thr=3
	for i in range(n):
		if lab[i]<0:
			lab[i]=thr
			thr+=3
print(*lab)