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
N=int(input())
P=[0 for i in range(N+1)]

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


d1=[10**9 for i in range(N+1)]
d1[1]=0
Q=[]
for i in L[1]:
    Q.append([i,1])


for i in range(N-1):
    d1[Q[i][0]]=Q[i][1]
    for j in L[Q[i][0]]:
        if d1[j]==10**9:
            Q.append([j,Q[i][1]+1])

ODD=0
EVE=0
for i in range(1,N+1):
    if d1[i]%2==0:
        EVE+=1
    else:
        ODD+=1

M1=[]
M2=[]
M3=[]
for i in range(1,N+1):
    if i%3==1:
        M1.append(i)
    elif i%3==2:
        M2.append(i)
    else:
        M3.append(i)
if min(ODD,EVE)*2<max(ODD,EVE):
    if ODD<EVE:
        D={}
        ans=[0 for i in range(N+1)]
        cnt=0
        for i in range(1,N+1):
            if d1[i]%2==1:
                ans[i]=M3[cnt]
                D[M3[cnt]]=1
                cnt+=1
        num=1
        for i in range(1,N+1):
            
            if d1[i]%2==0:
                if num in D:
                    
                    num+=1
                ans[i]=num
                num+=1
    else:
        D={}
        ans=[0 for i in range(N+1)]
        cnt=0
        for i in range(1,N+1):
            if d1[i]%2==0:
                ans[i]=M3[cnt]
                D[M3[cnt]]=1
                cnt+=1
        num=1
        for i in range(1,N+1):
            
            if d1[i]%2==1:
                if num in D:
                    
                    num+=1
                ans[i]=num
                num+=1
    print(*ans[1:])
else:
    ans=[0 for i in range(N+1)]
    m1=0
    m2=0
    m3=0
    for i in range(1,N+1):
        if d1[i]%2==0:
            if m1<len(M1):
                ans[i]=M1[m1]
                m1+=1
            else:
                ans[i]=M3[m3]
                m3+=1
        else:
            if m2<len(M2):
                ans[i]=M2[m2]
                m2+=1
            else:
                ans[i]=M3[m3]
                m3+=1
    print(*ans[1:])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
class Tree:
  C, RL = {}, {}
  R, N, D, S, P, T = None, None, None, None, None, None
  TL = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N 
    s.R[root] = 1
    s.RL[1] = [root] 
    s.S = {} 
    s.P = [-1] * s.N 
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i
      s.D += 1
      F = Ft
  def dfs(s, x, y, r): 
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False
  def dist(s, x): 
    t = [-1] * s.N
    S = [x]
    ans = x
    ansn = 0
    t[x] = 0
    while S != []:
      k = S.pop()
      for i in s.C[k]:
        if t[i] == -1:
          t[i] = t[k] + 1
          S.append(i)
          if t[i] > ansn:
            ansn = t[i]
            ans = i
    return ans, ansn
  def getDi(s, x = 0): 
    a, _ = s.dfs(x)
    b, ans = s.dfs(a)
    return ans
  def getDeep(s, x): 
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n): 
    if n == 0:
      return x
    if s.P[x] == -1:
      return -n
    return s.getParent(s.P[x], n - 1)
  def abList(s):
    A = []
    B = []
    for i in range(s.N):
      if s.R[i] % 2 == 0:
        A.append(i)
      else:
        B.append(i)
    if len(A) > len(B):
      return [B, A]
    else:
      return [A, B]



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

A = []
B = []
C = []

for i in range(1, N + 1):
  if i % 3 == 0:
    C.append(i)
  elif i % 3 == 1:
    A.append(i)
  else:
    B.append(i)

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

T.makeRank(0)

A, B = T.abList()

c = N // 3

Ans = [0] * N
if len(A) <= c:
  t = 3
  k = 1
  for i in A:
    Ans[i] = t
    t += 3
    c -= 1
  for i in range(N):
    if Ans[i] == 0:
      if c != 0:
        Ans[i] = t
        c -= 1
        t += 3
      else:
        Ans[i] = k
        k += 1
        if k % 3 == 0:
          k += 1
else:
  t = 3
  n = N // 3
  if N % 3 != 0:
    n += 1
  k = 1
  for i in range(n):
    Ans[A[i]] = k
    k += 3
  for i in range(n, len(A)):
    Ans[A[i]] = t
    t += 3
  n = N // 3
  if N % 3 == 2:
    n += 1
  k = 2
  for i in range(n):
    Ans[B[i]] = k
    k += 3
  for i in range(n, len(B)):
    Ans[B[i]] = t
    t += 3

print(" ".join(list(map(str, Ans))))

Solution (Python):
n=int(input())
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
ans=[0 for i in range(n+1)]
od=[1]
ev=[]
q=[1]
c=[1 for i in range(n+1)]
c[1]=0
t=0
while q:
    tl=q[:]
    q=[]
    for i in tl:
        for j in edge[i]:
            if c[j]:
                q.append(j)
                c[j]=0
                if t:
                    od.append(j)
                else:
                    ev.append(j)
    t^=1
if len(od)>len(ev):
    od,ev=ev,od
if len(od)<=n//3:
    t=3
    for i in od:
        ans[i]=t
        t+=3
    x=0
    for i,j in enumerate(ans):
        if j==0:
            ans[i]=x
            x+=1
            if x%3==0 and x<t:
                x+=1
else:
    t=0
    for i in range(1,n+1,3):
        ans[ev[t]]=i
        t+=1
    t=0
    for i in range(2,n+1,3):
        ans[od[t]]=i
        t+=1
    t=0
    for i,j in enumerate(ans):
        if j==0:
            ans[i]=t
            t+=3
print(" ".join(map(str,ans[1:])))

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

n = int(input())
ed = [tuple(map(int, input().split())) for _ in range(n-1)]
g = [list() for _ in range(n)]
for a,b in ed:
  g[a-1].append(b-1)
  g[b-1].append(a-1)
bi = [0]*n

def dfs(v, p):
  for x in g[v]:
    if x == p: continue
    bi[x] = 1 - bi[v]
    dfs(x, v)
  return


dfs(0,-1)
one = sum(bi)
two = n - one
if one < two:
  one, two = two, one
  bi = [1-x for x in bi]

on = 1
tw = 2
th = 3
ans = [0]*n
if two <= n//3:
  for i in range(n):
    if bi[i]:
      if on > n and tw > n:
        ans[i] = th
        th += 3
      elif on > n:
        ans[i] = tw
        tw += 3
      else:
        ans[i] = on
        on += 3
    else:
      ans[i] = th
      th += 3
  print(*ans)
  exit(0)

for i in range(n):
  if bi[i]:
    if on > n:
      ans[i] = th
      th += 3
    else:
      ans[i] = on
      on += 3
  else:
    if tw > n:
      ans[i] = th
      th += 3
    else:
      ans[i] = tw
      tw += 3
print(*ans)

Solution (Python):
import sys
import numpy as np
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))



N = ir()
graph = [[] for _ in range(N+1)] 
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

root = 1
rank = [0] * (N+1) 
rank[1] = 1
parent = [0] * (N+1) 
order = []
stack = [root]
while stack:
    cur = stack.pop()
    r = rank[cur]
    order.append(cur)
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        rank[next] = r + 1
        stack.append(next)

counter = [0, 0]
for x in rank[1:]:
    counter[x%2] += 1
num0mod3 = N // 2
num1mod3 = (N+2) // 3
num2mod3 = (N+1) // 3
answer = [0] * (N+1)
if max(counter) >= num1mod3 + num2mod3:
    
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 1
            if cur % 3 == 0:
                cur += 1
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
else:
    
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 2
    for i in range(1, N+1):
        if rank[i] % 2 == 1-index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)

print(*answer[1:])

Solution (Python):
from collections import deque


def solve(n, ab_list):
    g = [[] for _ in range(n + 1)]
    for a, b in ab_list:
        g[a].append(b)
        g[b].append(a)
    
    d_list = [-1] * (n + 1)
    d_list[1] = 0
    queue = deque([1])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if d_list[q] == -1:
                d_list[q] = d_list[p] + 1
                queue.append(q)
    
    cnt_2 = [0] * 6
    for i in range(1, n + 1):
        cnt_2[d_list[i] % 2] += 1

    if cnt_2[0] <= cnt_2[1]:
        min_01 = 0
    else:
        min_01 = 1

    min_sum = cnt_2[min_01]
    if min_sum <= n // 3:
        res_list = [0] * n
        list_3 = [3 * (k + 1) for k in range(min_sum)]
        list_other = [k for k in range(1, n + 1) if k % 3 != 0] + [3 * (k + 1) for k in range(min_sum, n // 3)]
        for i in range(1, n + 1):
            if d_list[i] % 2 == min_01:
                res_list[i - 1] = list_3.pop()
            else:
                res_list[i - 1] = list_other.pop()
    else:
        res_list = [0] * n
        add_1 = min_sum - (n + 2) // 3
        list_1 = [k + 1 for k in range(n) if k % 3 == 0] + [3 * (k + 1) for k in range(add_1)]
        list_2 = [k + 1 for k in range(n) if k % 3 == 1] + [3 * (k + 1) for k in range(add_1, n // 3)]
        for i in range(1, n + 1):
            if d_list[i] % 2 == min_01:
                res_list[i - 1] = list_1.pop()
            else:
                res_list[i - 1] = list_2.pop()

    return " ".join([str(r) for r in res_list])


def main():
    n = int(input())
    ab_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, ab_list)
    print(res)


def test():
    
    assert solve(5, [[1, 2], [1, 3], [3, 4], [3, 5]]) == "3 4 1 5 2"


if __name__ == "__main__":
    
    main()

Solution (Python):
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

E = [[] for _ in [0]*N]
for a,b in AB:
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)


D = dist_bfs(N,E,0)

e = []
o = []
cnt = 0
for i,d in enumerate(D):
    if d%2==0:
        e.append(i)
        cnt += 1
    else:
        o.append(i)
if cnt > N-cnt:
    e,o = o,e
    cnt = N-cnt
ans = [0]*N
if cnt <= N//3:
    done = set()
    j = 3
    for i in e:
        ans[i] = j
        done.add(j)
        j += 3
    j = 1
    for i in o:
        ans[i] = j
        j += 1
        while j in done:
            j += 1
else:
    done = set()
    j = 1
    for i in e:
        ans[i] = j
        done.add(j)
        j += 3
        if j > N: j = 3
    j = 2
    for i in o:
        ans[i] = j
        j += 1
        while j in done:
            j += 1
print(*ans)

Solution (Python):
import sys


def part(s, links):
    grp = [set(), set()]
    q = [(s, -1, 0)]
    while q:
        v, p, g = q.pop()
        grp[g].add(v)
        for u in links[v]:
            if u == p:
                continue
            q.append((u, v, g ^ 1))
    return grp


def solve(n, links):
    grp = part(0, links)
    can = [[], [], []]
    for i in range(1, n + 1):
        can[i % 3].append(i)
    
    

    if len(grp[0]) > len(grp[1]):
        grp[0], grp[1] = grp[1], grp[0]
    if len(can[1]) > len(can[2]):
        can[1], can[2] = can[2], can[1]

    ans = [0] * n

    if len(grp[0]) <= len(can[0]):
        for i, v in enumerate(grp[0]):
            ans[v] = can[0].pop()
        can = can[0] + can[1] + can[2]
        for i, v in enumerate(grp[1]):
            ans[v] = can.pop()
        return ans

    for i, v in enumerate(grp[0]):
        if can[1]:
            ans[v] = can[1].pop()
        else:
            ans[v] = can[0].pop()
    for i, v in enumerate(grp[1]):
        if can[2]:
            ans[v] = can[2].pop()
        else:
            ans[v] = can[0].pop()
    return ans


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print(*solve(n, links))

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


n,*ab = [int(i)-1 for i in read().split()]
n += 1
mp = iter(ab)

g = [[] for _ in range(n)]
for a,b in zip(mp,mp):
    g[a].append(b)
    g[b].append(a)

q = [0]
parent = [-1]*n
depth = [0]*n


while q:
    v = q.pop()
    d = depth[v]
    
    for c in g[v]:
        if c != parent[v]:
            q.append(c)
            parent[c] = v
            depth[c] = d+1

odd = [i for i,d in enumerate(depth) if d&1]
even = [i for i,d in enumerate(depth) if d&1==0]

s0 = list(range(3,n+1,3))
s1 = list(range(1,n+1,3))
s2 = list(range(2,n+1,3))

ans = [0]*n

m = n//3
if len(even) <= m:
    odd,even = even,odd

if len(odd) <= m:
    s2 += s1+s0
else:
    s2 += s0+s1

for i in odd:
    ans[i] = s2.pop()
for i in even:
    ans[i] = s2.pop()
    

print(*ans)

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

def dfs(s):
    stack = [s]
    used = set(s)
    dist = [0]*N
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                used.add(vf)
                dist[vf] = 1 + dist[vn]
                stack.append(vf)

N = int(readline())

zero = N//3
one = N//3 + int(N%3 >= 1)
two = N - zero - one



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



root = 0
col = [0]*N

stack = [root]
used = set(stack)
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf not in used:
            used.add(vf)
            col[vf] = 1 - col[vn]
            stack.append(vf)

if 2*sum(col) < N:
    col = [1-c for c in col]
black = sum(col)
white = N - black

Ans = [None]*N
remain = set(range(1, N+1))
if N <= 3:
    Ans = list(range(1, N+1))

elif white <= zero:
    zb = [i for i in range(1, N+1) if i%3 == 0]
    rb = [i for i in range(1, N+1) if i%3 != 0]
    for i in range(N):
        if col[i] == 0:
            Ans[i] = zb.pop()
    rb += zb
    for i in range(N):
        if col[i] == 1:
            Ans[i] = rb.pop()

elif one <= black and two <= white:
    zb = [i for i in range(1, N+1) if i%3 == 0]
    ob = [i for i in range(1, N+1) if i%3 == 1]
    tb = [i for i in range(1, N+1) if i%3 == 2]
    for i in range(N):
        if col[i] == 1:
            if ob:
                Ans[i] = ob.pop()
            else:
                Ans[i] = zb.pop()
        else:
            if tb:
                Ans[i] = tb.pop()
            else:
                Ans[i] = zb.pop()
else:
    assert False,''
print(*Ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
n = int(input())

edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even =[]
nums = [[],[],[]]
for i in range(1,n+1):
    nums[i % 3].append(i)

def dfs(x, last = -1, d = 0):
    if d % 2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:continue
        dfs(nxt, x, d + 1)

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

dfs(0)

zerocnt = len(nums[0])

if len(even) <= zerocnt:
    for even_node in even:
        ans[even_node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for odd_node in odd:
        ans[odd_node] = rest.pop()

elif len(odd) <= zerocnt:
    for odd_node in odd:
        ans[odd_node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for even_node in even:
        ans[even_node] = rest.pop()



else:
    for num in nums[1]:
        ans[even.pop()] = num
    for num in nums[2]:
        ans[odd.pop()] = num
    rest = nums[0]
    for even_node in even:
        ans[even_node] = rest.pop()
    for odd_node in odd:
        ans[odd_node] = rest.pop()

print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().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)
stack = [(1,1)]
color = [0]*(n+1)
while stack:
  x,c = stack.pop()
  color[x] = c
  for y in graph[x]:
    if color[y] == 0:
      stack.append((y,3-c))
ans = [0]*(n+1)
cnt1 = 1
cnt2 = 2
cnt3 = 3
if color.count(1) >= (n*2+2)//3:
  for i in range(1,n+1):
    if color[i] == 1:
      if cnt1 <= n:
        ans[i] = cnt1
        if cnt1%3 == 1:
          cnt1 += 1
        else:
          cnt1 += 2
      else:
        ans[i] = cnt3
        cnt3 += 3
    else:
      ans[i] = cnt3
      cnt3 += 3
elif color.count(2) >= (n*2+2)//3:
  for i in range(1,n+1):
    if color[i] == 2:
      if cnt1 <= n:
        ans[i] = cnt1
        if cnt1%3 == 1:
          cnt1 += 1
        else:
          cnt1 += 2
      else:
        ans[i] = cnt3
        cnt3 += 3
    else:
      ans[i] = cnt3
      cnt3 += 3
else:
  c1 = []
  c2 = []
  for i in range(1,n+1):
    if color[i] == 1:
      c1.append(i)
    else:
      c2.append(i)
  for x in c1:
    if cnt1 <= n:
      ans[x] = cnt1
      cnt1 += 3
    else:
      ans[x] = cnt3
      cnt3 += 3
  for x in c2:
    if cnt2 <= n:
      ans[x] = cnt2
      cnt2 += 3
    else:
      ans[x] = cnt3
      cnt3 += 3
ans = ans[1:]
print(*ans)

Solution (Python):
def examA():
    S = SI()
    if len(S)%2==1:
        print("No")
        return
    for i in range(len(S)//2):
        if S[i*2:i*2+2]!="hi":
            print("No")
            return
    print("Yes")
    return

def examB():
    a, b, M = LI()
    A = LI()
    B = LI()
    D = [LI()for _ in range(M)]
    ans = min(A) + min(B)
    for x,y,c in D:
        cur = A[x-1]+B[y-1]-c
        ans = min(ans,cur)
    print(ans)
    return

def examC():
    def bfs(n, e, fordfs):
        
        W = [-1] * n
        
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    L = bfs(N,0,V)
    
    odd = 0
    for l in L:
        if l==-1:
            print(-1)
            return
        if l%2==1:
            odd += 1
    G = []
    if odd*2<N:
        for i in range(N):
            if L[i]%2==1:
                G.append(i)
    else:
        for i in range(N):
            if L[i]%2==0:
                G.append(i)

    used = [False]*(N+1)
    ans = [0]*N
    if N//3>=len(G):
        cur = 3
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    else:
        cur = 1
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
            if cur>N:
                cur = 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    print(" ".join(map(str,ans)))
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examC()

"""

"""

Solution (Python):
from collections import defaultdict,deque,Counter
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a-= 1 ; b-=1
    lines[a].add(b)
    lines[b].add(a)


depths = [set() for _ in range(N)]
Ev = 0
Od = 0

def dfs(s,b,d):
    global depths
    global Ev
    global Od
    depths[d].add(s)

    if d%2 == 0:
        Ev += 1
    else:
        Od += 1

    for t in lines[s]:
        if t == b:
            continue
        else:
            dfs(t,s,d+1)


dfs(0,-1,0)



n1 = (N+2)//3
n2 = (N+1)//3
n0 = (N+0)//3


ansl = [-1]*N


if Ev <= n0 or Od <= n0:
    if Ev <= n0: fl = 0
    else: fl = 1

    for d, ps in enumerate(depths):
        if d%2 == fl:
            for p in ps:
                ansl[p] = n0*3
                n0 -= 1
        else:
            for p in ps:
                if n1 > 0:
                    ansl[p] = n1*3 - 2
                    n1 -= 1
                elif n2 > 0:
                    ansl[p] = n2*3 - 1
                    n2 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1
else:
    for d, ps in enumerate(depths):
        if d%2 == 0:
            for p in ps:
                if n1 > 0:
                    ansl[p] = n1*3 - 2
                    n1 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1
        else:
            for p in ps:
                if n2 > 0:
                    ansl[p] = n2*3 - 1
                    n2 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1

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

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):
from collections import deque
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
DE = [0] * N
e = 1
o = 0
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            DE[a] = DE[i] ^ 1
            if DE[a]:
                o += 1
            else:
                e += 1
            X[a].remove(i)
            deque.append(Q, a)

A = [i for i in range(1, N+1) if i % 3 == 1]
B = [i for i in range(1, N+1) if i % 3 == 2]
C = [i for i in range(1, N+1) if i % 3 == 0]

ANS = [-1] * N
if e <= len(C):
    for i in range(N):
        if DE[i] == 0:
            ANS[i] = C.pop()
    for i in range(N):
        if ANS[i] < 0:
            ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
elif o <= len(C):
    for i in range(N):
        if DE[i] == 1:
            ANS[i] = C.pop()
    for i in range(N):
        if ANS[i] < 0:
            ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
else:
    for i in range(N):
        if DE[i] == 0:
            ANS[i] = A.pop()
            if len(A) == 0: break
    for i in range(N):
        if DE[i] == 1:
            ANS[i] = B.pop()
            if len(B) == 0: break
    for i in range(N):
        if ANS[i] < 0:
            ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
    
print(*ANS)