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 = [tuple(map(int, input().split())) for _ in range(N - 1)]

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

    c1 = list(range(1, N + 1, 3))
    c2 = list(range(2, N + 1, 3))
    c3 = list(range(3, N + 1, 3))

    color = [0] * N

    for root in range(N):
        if len(to[root]) == 1:
            break

    queue = set([root])
    color[root] = 1
    while queue:
        v = queue.pop()
        color_v = color[v]
        for i in to[v]:
            if color[i] == 0:
                color[i] = 3 - color_v
                queue.add(i)

    ans = [0] * N
    order = sorted(range(N), key=lambda x: color[x])
    if color.count(1) <= N / 3:
        for i in order:
            if c3:
                ans[i] = c3.pop(-1)
            elif c1:
                ans[i] = c1.pop(-1)
            else:
                ans[i] = c2.pop(-1)
    elif color.count(2) <= N / 3:
        for i in reversed(order):
            if c3:
                ans[i] = c3.pop(-1)
            elif c1:
                ans[i] = c1.pop(-1)
            else:
                ans[i] = c2.pop(-1)
    else:
        for i in range(N):
            if (color[i] == 1) and c1:
                ans[i] = c1.pop(-1)
            elif (color[i] == 2) and c2:
                ans[i] = c2.pop(-1)
            else:
                ans[i] = c3.pop(-1)

    print(*ans)


main()

Solution (Python):
n = int(input())
con = [set() for _ in range(n)]
tree = [0]*n

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

checked = set([1])
stack = list(con[0])
stack_ = []
while len(checked) < n:
    while stack:
        x = stack.pop()
        if x in checked:
            continue
        checked.add(x)
        stack_.extend(con[x-1])
        tree[x-1] = 1
        
    while stack_:
        x = stack_.pop()
        if x in checked:
            continue
        checked.add(x)
        stack.extend(con[x-1])

mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    if (i+1)%3 == 0:
        mod0.append(i+1)
    elif (i+1)%3 == 1:
        mod1.append(i+1)
    else:
        mod2.append(i+1)

ans = [0]*n
sum_tree = sum(tree)
if sum_tree < n/3:
    for i in range(n):
        if tree[i] == 0:
            if mod1:
                ans[i] = mod1.pop()
            elif mod2:
                ans[i] = mod2.pop()
            else:
                ans[i] = mod0.pop()
        else:
            ans[i] = mod0.pop()
elif sum_tree > n*2/3:
    for i in range(n):
        if tree[i] == 1:
            if mod1:
                ans[i] = mod1.pop()
            elif mod2:
                ans[i] = mod2.pop()
            else:
                ans[i] = mod0.pop()
        else:
            ans[i] = mod0.pop() 
else:
    for i in range(n):
        if tree[i] == 0:
            if mod1:
                ans[i] = mod1.pop()
            else:
                ans[i] = mod0.pop()
        else:
            if mod2:
                ans[i] = mod2.pop()
            else:
                ans[i] = mod0.pop()
            
print(" ".join(map(lambda x:str(x), ans)))

Solution (Python):



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)


vertice = [-1 for _ in range(n)]
stack = [(0, 0)]

while stack:
    parent, vertex = stack.pop()
    vertice[vertex] = vertice[parent] * (-1)
    for next in edges[vertex]:
        if next != parent:
            stack.append((vertex, next))












ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(not3.pop()))
        else:
            if not3:
                ans.append(str(not3.pop()))
            else:
                ans.append(str(num3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(not3.pop()))
        else:
            if not3:
                ans.append(str(not3.pop()))
            else:
                ans.append(str(num3.pop()))
else:
    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]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]


graph = [[] for i in range(N + 1)]

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

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for k in range(1, N + 1):
    if k % 3 == 0:
        mod0.append(k)
    elif k % 3 == 1:
        mod1.append(k)
    else:
        mod2.append(k)

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


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N / 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N / 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod0:
                node_p[i] = mod0.pop()
            else:
                print(-1)
                exit(0)
        else:
            if mod2:
                node_p[i] = mod2.pop()
            elif mod0:
                node_p[i] = mod0.pop()
            else:
                print(-1)
                exit(0)

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(N)

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

for k in range(1, N + 1):
    modfit(k)

print()

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

Solution (Python):
import sys;input=sys.stdin.readline
N, = map(int, input().split())
G = [set() for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)

xs = [[] for _ in range(2)]
g2 = [set() for _ in range(N+1)]
vs = set()
stack = [1]
depth = [0]*(N+1)
dfs_vs = []
vs.add(1)
while stack:
    v = stack.pop()
    xs[depth[v] % 2].append(v)
    dfs_vs.append(v)
    for u in G[v]:
        if u in vs:
            continue
        depth[u] = depth[v] + 1
        g2[v].add(u)
        stack.append(u)
        vs.add(u)

xs.sort(key=lambda x:len(x))
rs = []
if len(xs[0]) <= N//3:
    i=j=k=0
    for x in xs[0]:
        i+=1
        rs.append((x, 3*i))
    for x in xs[1]:
        if i+1 <= N//3:
            i+=1
            rs.append((x, 3*i))
        elif j <= (N-1)//3:
            rs.append((x, 3*j+1))
            j+=1
        else:
            rs.append((x, 3*k+2))
            k+=1
else:
    i=j=k=0
    for x in xs[0]:
        if j <= (N-1)//3:
            rs.append((x, 3*j+1))
            j+=1
        elif i+1 <= N//3:
            i+=1
            rs.append((x, 3*i))
    for x in xs[1]:
        if i+1 <= N//3:
            i+=1
            rs.append((x, 3*i))
        else:
            rs.append((x, 3*k+2))
            k+=1


rs.sort(key=lambda x:x[0])
print(" ".join(str(x[1]) for x in rs))

Solution (Python):
n = int(input())
edge = [[] 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)
 
group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)
 
three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))

Solution (Python):
from collections import deque

def resolve():
    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)
    
resolve()

Solution (Python):
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
from collections import deque
l = [deque() for _ in range(N+1)]
ans = [0]*N
for a,b in ab:
  l[a].append(b)
  l[b].append(a)
  
r = [0]*(N+1)
i = 0
p = l[1]
q = deque()
flag = [False]*(N+1)
flag[1]=True
while (len(p)!=0)or(len(q)!=0):
  if i%2==0:
    while len(p)!=0:
      j = p.pop()
      if flag[j]:
        continue
      else:
        q.extend(l[j])
        flag[j]=True
        r[j]=1
    i+=1
  else:
    while len(q)!=0:
      j = q.pop()
      if flag[j]:
        continue
      else:
        p.extend(l[j])
        flag[j]=True
    i+=1
a = deque(range(1,N+1,3))
b = deque(range(2,N+1,3))
c = deque(range(3,N+1,3))
x = sum(r)
if x<=N//3:
  for i in range(1,N+1):
    if r[i]==1:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(b)!=0:
        ans[i-1]=b.pop()
      else:
        ans[i-1]=c.pop()
elif (N-x)<=N//3:
  for i in range(1,N+1):
    if r[i]==0:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(b)!=0:
        ans[i-1]=b.pop()
      else:
        ans[i-1]=c.pop()
else:
  for i in range(1,N+1):
    if r[i]==1:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(c)!=0:
        ans[i-1]=c.pop()
      else:
        ans[i-1]=b.pop()
    else:
      if len(b)!=0:
        ans[i-1]=b.pop()
      elif len(c)!=0:
        ans[i-1]=c.pop()
      else:
        ans[i-1]=a.pop()
        
print(' '.join(map(str,ans)))

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

N, *ab = map(int, read().split())

if N == 2:
    print(1, 2)
    exit()

graph = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)

k0 = list(range(3, N + 1, 3))
k1 = list(range(1, N + 1, 3))  
k2 = list(range(2, N + 1, 3))

start = ab[0]
color = 1  
queue = deque([(start, color)])
colors = [0] * (N + 1)
colors[start] = 1
while queue:
    V, c = queue.popleft()
    c = -c
    for v in graph[V]:
        if colors[v] == 0:
            colors[v] = c
            queue.append((v, c))

black = colors.count(1)
white = N - black
three = (N - 3) // 3 + 1
if black <= three:
    b = k0[:black]
    w = k1 + k2 + k0[black:]
    answer = [b.pop() if i == 1 else w.pop() for i in colors[1:]]
    print(' '.join(map(str, answer)))
elif white <= three:
    w = k0[:white]
    b = k1 + k2 + k0[white:]
    answer = [b.pop() if i == 1 else w.pop() for i in colors[1:]]
    print(' '.join(map(str, answer)))
else:
    answer = [0] * (N + 1)
    for i in range(1, N + 1):
        if colors[i] == 1:
            if k1:
                answer[i] = k1.pop()
            else:
                answer[i] = k0.pop()
        else:
            if k2:
                answer[i] = k2.pop()
            else:
                answer[i] = k0.pop()
    print(' '.join(map(str, answer[1:])))

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

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N = n_in()
edges = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = l_in()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)



S = []
depth = [0]*N
visited = set()

def dfs(v, d):
    visited.add(v)
    depth[v] = d
    S.append(v)
    for w in edges[v]:
        if w in visited:
            continue
        dfs(w, d+1)
        S.append(v)


root = 0
dfs(root, 0)

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

from collections import deque
q0 = deque(i for i in range(1,N+1) if i%3 == 0)
q1 = deque(i for i in range(1,N+1) if i%3 == 1)
q2 = deque(i for i in range(1,N+1) if i%3 == 2)

even_depth = len(list(filter(lambda d: d%2 == 0, depth)))
odd_depth = len(list(filter(lambda d: d%2 != 0, depth)))

if even_depth > N//3 and odd_depth > N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            if len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q0.popleft()
        else:
            if len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
elif even_depth <= N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q0.popleft()
        else:
            if len(q1) > 0:
                res[i] = q1.popleft()
            elif len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
else:
    for i, d in enumerate(depth):
        if d%2 != 0:
            res[i] = q0.popleft()
        else:
            if len(q1) > 0:
                res[i] = q1.popleft()
            elif len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()


print_l(res)

Solution (Python):
import sys
input = sys.stdin.readline
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())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

mod = [3, 1, 2]
ans = [0 for i in range(n)]
count = [0, 0]

def bfs(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        count[c % 2] += 1
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

def case1(cur, pre, c, i):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        t = c % 2
        if t == i:
            ans[cur] = mod[0]
            mod[0] += 3
        else:
            if mod[1] <= n:
                ans[cur] = mod[1]
                mod[1] += 3
            elif mod[2] <= n:
                ans[cur] = mod[2]
                mod[2] += 3
            else:
                ans[cur] = mod[0]
                mod[0] += 3
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

def case2(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        t = c % 2
        if mod[t+1] <= n:
            ans[cur] = mod[t+1]
            mod[t+1] += 3
        else:
            ans[cur] = mod[0]
            mod[0] += 3
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

bfs(0, -1, 0)

if count[0] <= n // 3:
    case1(0, -1, 0, 0)
elif count[1] <= n  // 3:
    case1(0, -1, 0, 1)
else:
    case2(0, -1, 0)

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

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

group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)

three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))

Solution (Python):
import sys
input = sys.stdin.readline
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())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

mod = [3, 1, 2]
ans = [0 for i in range(n)]
count = [0, 0]

def bfs(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        count[c % 2] += 1
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

def case1(cur, pre, c, i):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        t = c % 2
        if t == i:
            ans[cur] = mod[0]
            mod[0] += 3
        else:
            if mod[1] <= n:
                ans[cur] = mod[1]
                mod[1] += 3
            elif mod[2] <= n:
                ans[cur] = mod[2]
                mod[2] += 3
            else:
                ans[cur] = mod[0]
                mod[0] += 3
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

def case2(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        t = c % 2
        if mod[t+1] <= n:
            ans[cur] = mod[t+1]
            mod[t+1] += 3
        else:
            ans[cur] = mod[0]
            mod[0] += 3
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

bfs(0, -1, 0)

if count[0] < (n + 2)// 3:
    case1(0, -1, 0, 0)
elif count[1] < (n + 2) // 3:
    case1(0, -1, 0, 1)
else:
    case2(0, -1, 0)

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

Solution (Python):
import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

b=bfs(0)
ct0=0;ct1=0
for i in range(n):
  b[i]%=2
  if b[i]==0:
    ct0+=1
  else:
    ct1+=1

ans=[0]*n
x1=1;x2=2;x3=3

if ct0>=n//3+1 and ct1>=n//3+1:
  for i in range(n):
    if b[i]==0:
      if x1<=n:
        ans[i]=x1
        x1+=3
      else:
        ans[i]=x3
        x3+=3
    else:
      if x2<=n:
        ans[i]=x2
        x2+=3
      else:
        ans[i]=x3
        x3+=3

elif ct0<=n//3:
  for i in range(n):
    if b[i]==0:
      ans[i]=x3
      x3+=3
    else:
      if x1<=n:
        ans[i]=x1
        x1+=3
      elif x2<=n:
        ans[i]=x2
        x2+=3
      else:
        ans[i]=x3
        x3+=3

elif ct1<=n//3:
  for i in range(n):
    if b[i]==1:
      ans[i]=x3
      x3+=3
    else:
      if x1<=n:
        ans[i]=x1
        x1+=3
      elif x2<=n:
        ans[i]=x2
        x2+=3
      else:
        ans[i]=x3
        x3+=3

for i in range(n):
  ans[i]=str(ans[i])
print(' '.join(ans))

Solution (Python):
N = int(input())
from collections import defaultdict
flag = [0 for i in range(N)]
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)




from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)


al = [0, 0]
for d in dist:
    al[d%2] += 1
if sum(al) // al[0] >= 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            ansl.append(numbers3.pop())
        else:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
elif sum(al) // al[1] >= 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
else:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            if numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)

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

def dfs(v, u, d):
    if d % 2 == 0:
        even.append(v)
    else:
        odd.append(v)
    for i in g[v]:
        if i == u:
            continue
        dfs(i, v, d + 1)
    return

N = int(input())
g = [[] for _ in range(N)]
odd = []
even =[]
ans = [-1] * N
nums = [[], [], []]
for i in range(1, N + 1):
    nums[i % 3].append(i)
sanlst = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

dfs(0, -1, 0)
zCnt = len(nums[0])

if len(even) <= zCnt:
    for node in even:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in odd:
        ans[node] = rest.pop()
elif len(odd) <= zCnt:
    for node in odd:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in even:
        ans[node] = rest.pop()
else:
    for i in nums[1]:
        ans[even.pop()] = i
    for i in nums[2]:
        ans[odd.pop()] = i
    rest = nums[0]
    for i in even:
        ans[i] = rest.pop()
    for i in odd:
        ans[i] = rest.pop()

print(*ans)

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


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


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

ans = [None] * N
num0 = N // 3
num1 = N // 3 + (N % 3 >= 1)
num2 = N // 3 + (N % 3 == 2)
q0 = deque()
q1 = deque()
q = deque()
if node0 > num0 and node1 > num0:
    for i in range(1, num0 + 1):
        q.append(3 * i)
    for i in range(1, num1 + 1):
        q1.append(3 * i - 2)
    for i in range(1, num2 + 1):
        q0.append(3 * i - 1)
elif node0 <= num0:
    for i in range(1, node0 + 1):
        q0.append(3 * i)
    for i in range(node0 + 1, num0 + 1):
        q.append(3 * i)
    for i in range(1, num1 + 1):
        q1.append(3 * i - 2)
    for i in range(1, num2 + 1):
        q.append(3 * i - 1)
else:
    for i in range(1, node1 + 1):
        q1.append(3 * i)
    for i in range(node1 + 1, num0 + 1):
        q.append(3 * i)
    for i in range(1, num1 + 1):
        q.append(3 * i - 2)
    for i in range(1, num2 + 1):
        q0.append(3 * i - 1)

for i in range(N):
    if color[i] == 0:
        Q = q0 if q0 else q
        ans[i] = Q.pop()
    else:
        Q = q1 if q1 else q
        ans[i] = Q.pop()
print(*ans)

Solution (Python):
from collections import deque

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

queue = deque([1])
d, even_or_odd = 1, [1, 0]
while len(queue) > 0:
    newq = set()
    for _ in range(len(queue)):
        p = queue.pop()
        for q in edge[p]:
            if q != tree[p][0]:
                newq.add(q)
                tree[q][0], tree[q][1] = p, d % 2
    even_or_odd[d % 2] += len(newq)
    d += 1
    queue = deque(list(newq))

stock = [N//3] * 3
for i in range(N%3):    stock[i] += 1

if min(even_or_odd) > N//3:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0 and i <= stock[0] - 1:
            ans.append(3*i + 1)
            i += 1
        elif tree[l][1] != 0 and j <= stock[1] - 1:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
elif even_or_odd[0] <= stock[0] - 1:
    ans, num = [], [3*i for i in range(1, N//3 + 1)] + [i for i in range(N+1) if i % 3 != 0]
    i, j = 0, -1
    for k in range(1, N+1):
        if tree[k][1] == 0:
            ans.append(num[i])
            i += 1
        else:
            ans.append(num[j])
            j -= 1
else:
    ans, num = [], [3*i for i in range(1, N//3 + 1)] + [i for i in range(N+1) if i % 3 != 0]
    i, j = 0, -1
    for k in range(1, N+1):
        if tree[k][1] != 0:
            ans.append(num[i])
            i += 1
        else:
            ans.append(num[j])
            j -= 1
print(' '.join(map(str, ans)))