Problem:
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.

Incorrect submission (verdict: Wrong Answer):
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 len(A)<=n//3 or len(B)<=n//3:
    if len(A)>len(B):
        A,B=B,A
    qq=3
    for i in A:
        ans[i]=qq
        qq+=3
    qq=deque([3*i+1 for i in range(int(n/3+0.9999))]+[3*i+2 for i in range(int(n/3+0.9999))]+[3*i for i in range(int(n//3),-1,-1)])
    for t in range(n):
        if ans[t]!=0:
            ans[t]=qq.popleft()
            
    print(*ans)
    exit()
qq=deque([3*i+1 for i in range(int(n/3+0.9999))]+[3*i for i in range(int(n//3),0,-1)])
for i in A:
    ans[i]=qq.popleft()
qq.extend([3*i+2 for i in range(int(n/3+0.9999))])
for j in B:
    ans[j]=qq.pop()
print(*ans)


Fixed, accepted submission:
n=int(input())
dist=[-1]*n
G=[[] for i in range(n)]

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

from collections import deque
queue=deque([[0,i] for i in G[0]])
dist[0]=0
while queue:
    now,to=queue.pop()
    # print(now,to)
    if dist[to]!=-1:continue
    dist[to]=1-dist[now]
    for i in G[to]:
        queue.appendleft([to,i])

# print(dist)
q=sum(dist)
LAST=[0]*n
if n/3 <= q and n/3 <= n-q:
    
    A=[i for i in range(1,n+1,3)] + [0]*n
    

    B=[i for i in range(2,n+1,3)] + [0]*n


    now1=0
    now2=0
    for i in range(n):
        if dist[i]:
            LAST[i]=B[now2]
            now2+=1
        else:
            LAST[i]=A[now1]
            now1+=1
    w=3
    for i in range(n):
      if LAST[i]==0:
        LAST[i]=w
        w+=3
    print(*LAST)
            
elif n/3 >q:
    w=3
    for i in range(n):
        if dist[i]:
            LAST[i]=w
            w+=3
    A=[i for i in range(w,n+1,3)]+[i for i in range(1,n+1) if i%3!=0]
    now=0
    for i in range(n):
        if LAST[i]==0:
            LAST[i]=A[now]
            now+=1
    print(*LAST)
else:
    w=3
    for i in range(n):
        if dist[i]==0:
            LAST[i]=w
            w+=3
    A=[i for i in range(w,n+1,3)]+[i for i in range(1,n+1) if i%3!=0]
    now=0
    for i in range(n):
        if LAST[i]==0:
            LAST[i]=A[now]
            now+=1
    print(*LAST)