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):
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
input = sys.stdin.readline

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
group = [-1] * N
count = [0] * 2
stack = []
group[0] = 0
count[0] = 1
stack.append(0)
while stack:
    u = stack.pop()
    for v in G[u]:
        if group[v] == -1:
            group[v] = 1 - group[u]
            count[group[v]] += 1
            stack.append(v)
zeros = list(range(3, N+1, 3))
ones = list(range(1, N+1, 3))
twos = list(range(2, N+1, 3))
ans = [0] * N
for g in range(2):
    if count[g] <= N//3:
        for i in range(N):
            if group[i] == g:
                ans[i] = zeros.pop()
            else:
                if len(twos) > 0:
                    ans[i] = twos.pop()
                elif len(ones) > 0:
                    ans[i] = ones.pop()
                else:
                    ans[i] = zeros.pop()
        print(' '.join(map(str, ans)))
        exit()
for i in range(N):
    if group[i] == 0 and len(ones) > 0:
        ans[i] = ones.pop()
    elif group[i] == 1 and len(twos) > 0:
        ans[i] = twos.pop()
    else:
        ans[i] = zeros.pop()
print(' '.join(map(str, ans)))

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


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

Cl = [-1]*N
C = [[0], []]
q = [0]
c = 0
Cl[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np in graph[p]:
            if Cl[np]  == -1:
                Cl[np] = c
                C[c].append(np)
                qq.append(np)
    q = qq

if len(C[0]) > len(C[1]):
    C = [C[1], C[0]]

c0 = (N+2)//3
c1 = (N+1)//3
c2 = N//3
Co = [[], [], []]
if len(C[0]) < c1:
    R = set(C[0])
    for r in R:
        Co[2].append(r)
    for p in range(N):
        if p in R:
            continue
        elif len(Co[0]) < c0:
            Co[0].append(p)
        elif len(Co[1]) < c1:
            Co[1].append(p)
        else:
            Co[2].append(p)













else:
    R2 = set(C[1])
    for p in range(N):
        if p in R2: 
            if len(Co[0]) < c0:
                Co[0].append(p)
            else:
                Co[2].append(p)
        else: 
            if len(Co[1]) < c1:
                Co[1].append(p)
            else:
                Co[2].append(p)

ans = [None]*N
for i, n in enumerate(Co[0]):
    ans[n] = 3*i+1
for i, n in enumerate(Co[1]):
    ans[n] = 3*i+2
for i, n in enumerate(Co[2]):
    ans[n] = 3*i+3


print(*ans)

Solution (Python):
from collections import Counter
def main():
    N=int(input())
    AB=[list(map(int, input().split())) for _ in range(N-1)]
    G=[[]for _ in range(N)]
    cnt=[0]*N
    for a,b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cnt[a-1]+=1
        cnt[b-1]+=1
    CI=sorted(((c,i) for i,c in enumerate(cnt)), reverse=True)
    ans=[0]*N
    C=[0]*N
    stack=[(0,-1,0)]
    while stack:
        u,p,d=stack.pop()
        for v in G[u]:
            if v!=p:
                stack.append((v,u,d^1))
                C[v]=d^1
    X=sum(C)
    if X<=N//3:
        D=[[i for i in range(1,N+1,3)]+[i for i in range(2,N+1,3)],[i for i in range(3,N+1,3)]]
        for i in range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[C[i]^1].pop()
    elif N-X<=N//3:
        D=[[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 range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[C[i]^1].pop()
    else:
        D=[[i for i in range(1,N+1,3)],[i for i in range(2,N+1,3)],[i for i in range(3,N+1,3)]]
        for i in range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[2].pop()
    print(*ans)

if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.buffer.readline

from collections import defaultdict
import queue


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

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"


def main():
	N = int(input())
	
	a0 = int(N // 3)
	a1 = int((N + 2) // 3)
	a2 = int((N + 1) // 3)

	
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	
	BF = BFS(G, 0, N)
	dist = BF.dist
	dis_even = 0
	dis_odd = 0
	for i in range(N):
		if dist[i] % 2 == 0:
			dis_even += 1
		else:
			dis_odd += 1

	ans = [0] * N
	judge = "No"
	S = [(i + 1) * 3 for i in range(a0)] + [i * 3 + 1 for i in range(a1)] + [i * 3 + 2 for i in range(a2)]
	if a2 <= dis_odd and a1 <= dis_even:
		judge = "Yes"
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a2:
					ans[i] = c1 * 3 + 2
					c1 += 1
			else:
				if c2 < a1:
					ans[i] = c2 * 3 + 1
					c2 += 1

		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1

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

	elif a1 <= dis_odd and a2 <= dis_even:
		judge = "Yes"
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a1:
					ans[i] = c1 * 3 + 2
					c1 += 1
			else:
				if c2 < a2:
					ans[i] = c2 * 3 + 1
					c2 += 1

		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1

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

	elif dis_odd <= a0:
		cnt = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				ans[i] = S[cnt]
				cnt += 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = S[cnt]
				cnt += 1

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

	else:
		cnt = 0
		for i in range(N):
			if dist[i] % 2 == 0:
				ans[i] = S[cnt]
				cnt += 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = S[cnt]
				cnt += 1

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

if __name__ == '__main__':
	main()

Solution (Python):
from collections import deque

N = int(input())
tree = [[] for i 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)

d = deque([[0, -1]])
dist = [0] * N
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dist[child] = (dist[node] + 1) % 2
    d.appendleft([child, node])

count0 = dist.count(0)
count1 = N - count0
s = [set(), set(), set()]
for i in range(1, N+1):
  s[i%3].add(i)
if count0 > N//3:
  if count1 > N//3:
    for i in range(N):
      if dist[i]:
        if s[2]:
          dist[i] = s[2].pop()
        else:
          dist[i] = s[0].pop()
      else:
        if s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
  else:
    for i in range(N):
      if dist[i]:
        dist[i] = s[0].pop()
      else:
        if s[2]:
          dist[i] = s[2].pop()
        elif s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
else:
  for i in range(N):
    if dist[i]:
      if s[2]:
        dist[i] = s[2].pop()
      elif s[1]:
        dist[i] = s[1].pop()
      else:
        dist[i] = s[0].pop()
    else:
      dist[i] = s[0].pop()

print(*dist)

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = lr()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    one = N//3+min(1, N%3)
    two = N//3+N%3//2
    thr = N//3
    ans = [0]*N
    ball = [0]*N
    cnt = 0
    dist = [-1]*N
    s = [0]
    dist[0] = 0
    while len(s) > 0:
        v = s.pop()
        for j in edges[v]:
            if dist[j] == -1:
                dist[j] = dist[v]+1
                if dist[j]%2 == 1:
                    ball[j] = 1
                    cnt += 1
                s.append(j)
    if cnt > N/3 and N-cnt > N/3:
        for i in range(N):
            if ball[i] == 1:
                ans[i] = 3*one-2
                one -= 1
            else:
                ans[i] = 3*two-1
                two -= 1
        for i in range(N):
            if ans[i] <= 0:
                ans[i] = 3*thr
                thr -= 1
    elif cnt <= N/3:
        for i in range(N):
            if ball[i] == 1:
                ans[i] = 3*thr
                thr -= 1
        for i in range(N):
            if ans[i] <= 0:
                if thr > 0:
                    ans[i] = 3*thr
                    thr -= 1
                elif two > 0:
                    ans[i] = 3*two-1
                    two -= 1
                else:
                    ans[i] = 3*one-2
                    one -= 1
    else:
        for i in range(N):
            if ball[i] == 0:
                ans[i] = 3*thr
                thr -= 1
        for i in range(N):
            if ans[i] <= 0:
                if thr > 0:
                    ans[i] = 3*thr
                    thr -= 1
                elif two > 0:
                    ans[i] = 3*two-1
                    two -= 1
                else:
                    ans[i] = 3*one-2
                    one -= 1
    print(*ans, sep=' ') 
resolve()

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
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)

inf=float("inf")

prv=[inf]*n
prv[0]=-1
depth=[inf]*n
depth[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next in edge[cur]:
    if prv[next]==inf:
      prv[next]=cur
      depth[next]=depth[cur]+1
      stack.append(next)
e,o=0,0
for i in range(n):
  if depth[i]%2:
    o+=1
  else:
    e+=1
Ans=[0]*n
if e<=n//3:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if not depth[i]%2:
      Ans[i]=3*ct3+3
      ct3+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      elif 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
elif o<=n//3:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if depth[i]%2:
      Ans[i]=3*ct3+3
      ct3+=1
    else:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      elif 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
else:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if not depth[i]%2:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1

print(*Ans)

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

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

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += 1
                self.dfs(v)
                self.depth -= 1

        self.colors[u] = self.BLACK


tree = Tree(adj)
tree.dfs(0)

ev = [i for i, e in enumerate(tree.depths) if e % 2 == 0]
od = [i for i, e in enumerate(tree.depths) if e % 2]

l_ev = len(ev)
l_od = len(od)

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

ans = [0] * n


def f(li1, li2):
    while li1 and li2:
        i = li1.pop()
        num = li2.pop()
        ans[i] = num


if l_ev > n / 3 and l_od > n / 3:
    f(ev, mod1)
    f(od, mod2)
    f(ev, mod0)
    f(od, mod0)

elif l_ev <= n / 3:
    f(ev, mod0)
    f(od, mod0)
    f(od, mod1)
    f(od, mod2)

else:
    f(od, mod0)
    f(ev, mod0)
    f(ev, mod1)
    f(ev, mod2)

print(*ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import queue

def main():
    N=I()
    adj=[[] for _ in range(N)]
    mod1=range(1,N+1,3)
    n1=0
    mod2=range(2,N+1,3)
    n2=0
    mod12=list(mod1)+list(mod2)
    n12=0
    mod3=range(3,N+1,3)
    n3=0
    
    p=[0]*N
    
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
     
    
    q=queue.Queue()
    q.put((0,-1,0))
    d=[0]*N
            
        
    while not q.empty():
        v,par,depth=q.get()
        d[v]=depth%2
                
        for i in range(len(adj[v])):
            nxt=adj[v][i]
            if nxt!=par:
                q.put((nxt,v,depth+1))
                
    dmod=[0,0]
    for i in range(N):
        dmod[d[i]]+=1
        
    if dmod[0]<=(N//3):
        for i in range(N):
            if d[i]==0:
                p[i]=mod3[n3]
                n3+=1
            else:
                if n12<len(mod12):
                    p[i]=mod12[n12]
                    n12+=1
                else:
                    p[i]=mod3[n3]
                    n3+=1
    elif dmod[1]<=(N//3):
        for i in range(N):
            if d[i]==1:
                p[i]=mod3[n3]
                n3+=1
            else:
                if n12<len(mod12):
                    p[i]=mod12[n12]
                    n12+=1
                else:
                    p[i]=mod3[n3]
                    n3+=1         
    
    else:
        for i in range(N):
            if d[i]==1:
                if n1<len(mod1):
                    p[i]=mod1[n1]
                    n1+=1
                else:
                    p[i]=mod3[n3]
                    n3+=1
            else:
                if n2<len(mod2):
                    p[i]=mod2[n2]
                    n2+=1
                else:
                    p[i]=mod3[n3]
                    n3+=1     
    
                
    print(' '.join(map(str, p)))
        
        
    
    
        
                
            
        
        
    

main()

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    Par = [0 for _ in range(N)]
    Son = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    Dist = [0] * N
    DistType = [0, 0]
    q = deque()
    q.append((0, 0, 0)) 
    modCount = [N // 3, N // 3, N // 3]
    if N % 3 == 1: modCount[1] += 1
    elif N % 3 == 2:
        modCount[1] += 1
        modCount[2] += 1
    modIndex = [0, 0, 0]
    search = deque()
    while q:
        nowNode, preNode, dist = q.popleft()
        Dist[nowNode] = dist
        Par[nowNode] = preNode
        Son[preNode].append(nowNode)
        search.append(nowNode)
        DistType[dist % 2] += 1
        for nextNode in Edge[nowNode]:
            if nextNode != preNode: q.append((nextNode, nowNode, dist + 1))
    Ans = [-1] * N
    if DistType[0] <= modCount[0]:
        for i, d in enumerate(Dist):
            if d % 2 == 0:
                Ans[i] = 3 * modIndex[0] + 3
                modIndex[0] += 1
            else:
                if modIndex[1] < modCount[1]:
                    Ans[i] = 3 * modIndex[1] + 1
                    modIndex[1] += 1
                elif modIndex[2] < modCount[2]:
                    Ans[i] = 3 * modIndex[2] + 2
                    modIndex[2] += 1
                else:
                    Ans[i] = 3 * modIndex[0] + 3
                    modIndex[0] += 1
    elif DistType[1] <= modCount[0]:
        for i, d in enumerate(Dist):
            if d % 2 == 1:
                Ans[i] = 3 * modIndex[0] + 3
                modIndex[0] += 1
            else:
                if modIndex[1] < modCount[1]:
                    Ans[i] = 3 * modIndex[1] + 1
                    modIndex[1] += 1
                elif modIndex[2] < modCount[2]:
                    Ans[i] = 3 * modIndex[2] + 2
                    modIndex[2] += 1
                else:
                    Ans[i] = 3 * modIndex[0] + 3
                    modIndex[0] += 1
    else:
        for i, d in enumerate(Dist):
            if d % 2 == 0:
                if modIndex[1] < modCount[1]:
                    Ans[i] = 3 * modIndex[1] + 1
                    modIndex[1] += 1
                else:
                    Ans[i] = 3 * modIndex[0] + 3
                    modIndex[0] += 1
            else:
                if modIndex[2] < modCount[2]:
                    Ans[i] = 3 * modIndex[2] + 2
                    modIndex[2] += 1
                else:
                    Ans[i] = 3 * modIndex[0] + 3
                    modIndex[0] += 1
    print(" ".join(map(str, Ans)))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from sys import setrecursionlimit

setrecursionlimit(10**6)

def dfs(i, depth):
    visited[i] = True
    oe = depth%2
    ans[i-1] = oe
    count[oe] += 1
    nodes = tree[i]
    for node in nodes:
        if visited[node]:
            continue
        dfs(node, depth+1)
    


N = int(input())
ans = [-1]*N
tree = [[] for i in range(N+1)]
visited = [False]*(N+1)
count = [0, 0]
base = [1, 2, 3]
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a] += [b]
    tree[b] += [a]
dfs(1, 0)
even_len = count[0]
odd_len = count[1]
if even_len > N//3 and odd_len > N//3:
    for i, oe in enumerate(ans):
        if base[oe] > N:
            ans[i] = str(base[2])
            base[2] += 3
        else:
            ans[i] = str(base[oe])
            base[oe] += 3
elif even_len <= N//3:
    for i, oe in enumerate(ans):
        if oe == 0:
            ans[i] = str(base[2])
            base[2] += 3
        elif base[0] <= N:
            ans[i] = str(base[0])
            base[0] += 3
        elif base[1] <= N:
            ans[i] = str(base[1])
            base[1] += 3
        else:
            ans[i] = str(base[2])
            base[2] += 3
elif odd_len <= N//3:
    for i, oe in enumerate(ans):
        if oe == 1:
            ans[i] = str(base[2])
            base[2] += 3
        elif base[0] <= N:
            ans[i] = str(base[0])
            base[0] += 3
        elif base[1] <= N:
            ans[i] = str(base[1])
            base[1] += 3
        else:
            ans[i] = str(base[2])
            base[2] += 3
print(' '.join(ans))

Solution (Python):
import sys
sys.setrecursionlimit(10**5+1)

def cur(p):
    for i in x[p]:
        if rank[i]==-1:
            rank[i]=rank[p]+1
            par[i]=p
            cur(i)


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

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

rank=[-1 for i in range(n)]
rank[0]=0
par=[-1 for i in range(n)]

cur(0)
M=max(rank)
x=[[] for i in range(M+1)]

q=[0,0]
r=[n//3,n//3,n//3]
if n%3>0: r[1]+=1
if n%3>1: r[2]+=1
tmp1,tmp2,tmp3=1,2,3

for i in range(n):
    q[rank[i]%2]+=1
    x[rank[i]].append(i)
ans=[-1 for i in range(n)]

"""
if q[0]>r[0]+r[1] or q[1]>r[0]+r[2]:
    if q[0]>r[0]+r[2] or q[1]>r[0]+r[1]:
        tmp1,tmp2=2,1
"""

if q[0]<=r[0]+r[1] and q[1]<=r[0]+r[2]:
    for i in range(n):
        if rank[i]%2==0:
            if tmp1<=n:
                ans[i]=tmp1
                tmp1+=3
            else:
                ans[i]=tmp3
                tmp3+=3
        else:
            if tmp2<=n:
                ans[i]=tmp2
                tmp2+=3
            else:
                ans[i]=tmp3
                tmp3+=3

elif q[0]<=r[0]:
    for i in range(n):
        if rank[i]%2==0:
            ans[i]=tmp3
            tmp3+=3
        else:
            if tmp1<=n:
                ans[i]=tmp1
                tmp1+=3
            elif tmp2<=n:
                ans[i]=tmp2
                tmp2+=3
            else:
                ans[i]=tmp3
                tmp3+=3

elif q[1]<=r[0]:
    for i in range(n):
        if rank[i]%2==1:
            ans[i]=tmp3
            tmp3+=3
        else:
            if tmp1<=n:
                ans[i]=tmp1
                tmp1+=3
            elif tmp2<=n:
                ans[i]=tmp2
                tmp2+=3
            else:
                ans[i]=tmp3
                tmp3+=3

    

for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Solution (Python):
from heapq import heappop as he
n=int(input())
s=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    s[a].append(b)
    s[b].append(a)
c=[0]*n
q=[1]
t=[1]*n
t[1]=0
fl=0
while q:
    fl^=1
    p=[]
    for j in q:
        for h in s[j]:
            if t[h]:
                t[h]=0
                c[h]=fl
                p.append(h)
    q=p.copy()
if c.count(1)>n//3 and c.count(0)>n//3:
    p,q,r=1,2,3
    for i in range(n):
        if c[i]:
            if q<=n:
                c[i]=q
                q+=3
            else:
                c[i]=r
                r+=3
        else:
            if p<=n:
                c[i]=p
                p+=3
            else:
                c[i]=r
                r+=3
elif c.count(1)<=n//3:
    p,q,r=1,2,3
    for i in range(n):
        if c[i]:
            c[i]=r
            r+=3
        else:
            if p<=n:
                c[i]=p
                p+=3
            elif q<=n:
                c[i]=q
                q+=3
            else:
                c[i]=r
                r+=3
else:
    p,q,r=1,2,3
    for i in range(n):
        if not c[i]:
            c[i]=r
            r+=3
        else:
            if q<=n:
                c[i]=q
                q+=3
            elif p<=n:
                c[i]=p
                p+=3
            else:
                c[i]=r
                r+=3
print(*c)

Solution (Python):
from collections import deque


n = int(input())

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


root = 0
visited = [-1] * n
def dfs(root):
    q = deque([root])
    visited[root] = 0
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v] != -1:
                continue
            else:
                visited[nxt_v] = (visited[v] + 1) % 2
                q.append(nxt_v)
dfs(0)
cnt0 = 0
cnt1 = 0
for i in range(n):
    if visited[i] == 0:
        cnt0 += 1
    else:
        cnt1 += 1

num1 = n // 3 
num2 = n // 3
num3 = n // 3
if n % 3 >= 1:
   num1 += 1
if n % 3 >= 2:
   num2 += 1
    
ans = [0] * n

set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
    if i % 3 == 0:
        set3.add(i)
    elif i % 3 == 1:
        set1.add(i)
    elif i % 3 == 2:
        set2.add(i)
        
if cnt0 <= num3:
    for i in range(n):
        if visited[i] == 0:
            ans[i] = set3.pop()
        else:
            if set1:
                ans[i] = set1.pop() 
            elif set2:
                ans[i] = set2.pop()         
            elif set3:
                ans[i] = set3.pop()  

elif cnt1 <= num3:
    for i in range(n):
        if visited[i] == 1:
            ans[i] = set3.pop()
        else:
            if set1:
                ans[i] = set1.pop() 
            elif set2:
                ans[i] = set2.pop()         
            elif set3:
                ans[i] = set3.pop()  
else:
    num147 = 0
    num258 = 0
    num369 = 0
    for i in range(n):
        if visited[i] == 0:
            num = num147 * 3 + 1
            if num > n:
                num = num369 * 3 + 3
                ans[i] = num
                if num > n:
                    error
                    exit()
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num 
            set1.remove(num)
            num147 += 1
        else:
            num = num258 * 3 + 2 
            if num > n:
                num = num369 * 3 + 3
                if num > n:
                    error
                    exit()
                ans[i] = num
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num 
            set2.remove(num)
            num258 += 1
     
    for i in range(n):
        if ans[i] == 0:
            if set1:
                ans[i] = set1.pop()
            elif set2:
                ans[i] = set2.pop()
            elif set3:
                ans[i] = set3.pop()
print(*ans)

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

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
L = [-1]*n
dist = [-1]*n
dist[0] = 0
F_1 = [i for i in range(1, n+1) if i%3==1]
F_2 = [i for i in range(1, n+1) if i%3==2]
F_0 = [i for i in range(1, n+1) if i%3==0]
def dfs(v):
  for nv in T[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v] ^ 1
      dfs(nv)
dfs(0)
l0 = dist.count(0)
l1 = n - l0
if l0 <= n//3:
  for i in range(n):
    if dist[i] == 0:
      L[i] = F_0.pop()
    else:
      if F_1:
        L[i] = F_1.pop()
      elif F_2:
        L[i] = F_2.pop()
      else:
        L[i] = F_0.pop()
elif l1 <= n//3:
  for i in range(n):
    if dist[i]:
      L[i] = F_0.pop()
    else:
      if F_1:
        L[i] = F_1.pop()
      elif F_2:
        L[i] = F_2.pop()
      else:
        L[i] = F_0.pop()
else:
  for i in range(n):
    if dist[i]:
      if F_1:
        L[i] = F_1.pop()
      else:
        L[i] = F_0.pop()
    else:
      if F_2:
        L[i] = F_2.pop()
      else:
        L[i] = F_0.pop()
print(*L)