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.



Sample input:
5
1 2
1 3
3 4
3 5


Sample output:
1 2 5 4 3

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    from heapq import heappush, heappop
    import sys
    input = sys.stdin.readline

    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    def bfs3(s):
        dq = deque()
        dq.append(s)
        dist = [-1] * N
        dist[s] = 0

        dist3 = set()
        while dq:
            v = dq.popleft()
            d = dist[v]
            for u in graph[v]:
                if ~dist[u]: continue
                dist[u] = d + 1
                if d == 2:
                    dist3.add(u)
                else:
                    dq.append(u)

        return dist3

    # solve
    dist3s = []
    h = []
    deg = [0] * N
    for v in range(N):
        res = bfs3(v)
        dist3s.append(res)
        d_ = len(res)
        deg[v] = d_
        if d_:
            heappush(h, (-d_, v))

    ret = [-1] * N
    need_update = [0] * N
    need = [-1] * N

    m3 = 3
    m2 = 2
    m1 = 1
    while h:
        d, v = heappop(h)
        if need_update[v]:
            heappush(h, (-deg[v], v))
            need_update[v] = 0
            continue

        if need[v] == 0:
            if m1 // 3 < m2 // 3:
                if m1 > N:
                    if m3 <= N:
                        ret[v] = m3
                        m3 += 3
                        for u in dist3s[v]:
                            deg[u] -= 1
                            need_update[u] = 1
                            need[u] = 0
                    else:
                        print(-1)
                        return
                else:
                    ret[v] = m1
                    m1 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 2  # 2


            else:
                if m2 > N:
                    if m3 <= N:
                        ret[v] = m3
                        m3 += 3
                        for u in dist3s[v]:
                            deg[u] -= 1
                            need_update[u] = 1
                            need[u] = 0
                    else:
                        print(-1)
                        return
                else:
                    ret[v] = m2
                    m2 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 1  # 1

        elif need[v] == 2:
            if m2 > N:
                if m3 <= N:
                    ret[v] = m3
                    m3 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 0
                else:
                    print(-1)
                    return
            else:
                ret[v] = m2
                m2 += 3
                for u in dist3s[v]:
                    deg[u] -= 1
                    need_update[u] = 1
                    need[u] = 1  # 1

        elif need[v] == 1:
            if m1 > N:
                if m3 <= N:
                    ret[v] = m3
                    m3 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 0
                else:
                    print(-1)
                    return
            else:
                ret[v] = m1
                m1 += 3
                for u in dist3s[v]:
                    deg[u] -= 1
                    need_update[u] = 1
                    need[u] = 2  # 2

        else:
            if m3 <= N:
                ret[v] = m3
                m3 += 3
                for u in dist3s[v]:
                    deg[u] -= 1
                    need_update[u] = 1
                    need[u] = 0  # なんでも
            else:
                if m1 // 3 < m2 // 3:
                    if m1 > N:
                        print(-1)
                        return

                    ret[v] = m1
                    m1 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 2  # 2

                else:
                    if m2 > N:
                        print(-1)
                        return

                    ret[v] = m2
                    m2 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 1  # 1

    for v in range(N):
        if ret[v] == -1:
            if m1 <= N:
                ret[v] = m1
                m1 += 3
            elif m2 <= N:
                ret[v] = m2
                m2 += 3
            elif m3 <= N:
                ret[v] = m3
                m3 += 3
            else:
                print(-1)
                return

    print(*ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
E = [[] for _ in range(N+1)]
 
for i in range(N-1):
  a,b = map(int,input().split())
  E[a].append(b)
  E[b].append(a)

ans = [0] * (N+1)

q = [[1,1]]

while q:
	cp,cd = q.pop(0)
	for np in E[cp]:
		if ans[np] == 0:
			ans[np] = cd*(-1)
			q.append([np,cd*(-1)])

print(-1)
#mod0 = 6
#mod1 = 1
#mod2 = 2

#answer = [3]
#for i in range(2,N+1):
#	if ans[i] == 1:
#		if mod1 <= N:
#			answer.append(mod1)
#			mod1 += 3
#		else:
#			answer.append(mod0)
#			mod0 += 3
#	else:
#		if mod2 <= N:
#			answer.append(mod2)
#			mod2 += 3
#		else:
#			answer.append(mod0)
#			mod0 += 3

#print(*answer)

Submission status: Wrong Answer

Solution code:
n=int(input())
l1=[set() for i in range(n+1)]
l2=[set() for i in range(n+1)]
l3=[set() for i in range(n+1)]

for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    l1[a].add(b)
    l1[b].add(a)

for i in range(1,1+n):
    for j in l1[i]:
        l2[i]^=l1[j]
    if i in l2[i]:
        l2[i].remove(i)

for i in range(1,1+n):
    for j in l2[i]:
        l3[i]^=l1[j]
    l3[i]-=l1[i]

l=set()
for i in range(1,1+n):
    for j in l3[i]:
        p,q=min(i,j),max(i,j)
        l.add((p-1,q-1))

ans=[0]*n
s1=list(range(1,n+1,3))
s2=list(range(2,n+1,3))
s3=list(range(3,n+1,3))
p,q,r=0,0,0
s,t,u=len(s1),len(s2),len(s3)
import collections
ll=collections.Counter() 
for i,j in l:
    ll[i]+=1
    ll[j]+=1
lll=ll.most_common()
for x,y in lll[::-1]:
    i=int(x)
    for j in l3[i+1]:
        j-=1
        if ans[i]==0 and ans[j]==0:
            if p<s and q<t:
                ans[i]=s1[p]
                ans[j]=s2[q]
                p+=1
                q+=1
            else:
                if p<s:
                    ans[i]=s1[p]
                    p+=1
                    if r<u:
                        ans[j]=s3[r]
                        r+=1
                    else:
                        print(-1)
                        exit()
                elif q<t:
                    ans[j]=s1[p]
                    p+=1
                    if r<u:
                        ans[i]=s3[r]
                        r+=1
                    else:
                        print(-1)
                        exit()
                else:
                    if r<u-1:
                        ans[i]=s3[r]
                        ans[j]=s3[r+1]
                        r+=2
                    else:
                        print(-1)
                        exit()

for i in range(n):
    if ans[i]==0:
        if p<s:
            ans[i]=s1[p]
            p+=1
        elif q<t:
            ans[i]=s2[q]
            q+=1
        elif r<u:
            ans[i]=s3[r]
            r+=1
        else:
            print(-1)
            exit()


print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
import copy
sys.setrecursionlimit(10**6)
def dfs(tree, cursor, parent):
  rtn = deque()
  for child in tree[cursor]:
    notme = copy.copy(tree[cursor])
    notme.remove(child)
    for mago in tree[child]:
      if parent != 0:
        rtn.append((parent, mago))
        rtn += deque([(c2, mago) for c2 in notme])
    rtn += dfs(tree, child, cursor)
  return rtn

N = int(input())
T = [deque() for _ in range(N+1)]
seen = [False]*(N+1)
a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
T[a].append(b)
seen[a] = True
seen[b] = True
for _ in range(N-2):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  if not seen[a]:
    T[b].append(a)
  else:
    T[a].append(b)
  seen[a] = True
  seen[b] = True
dist3s = dfs(T, 1, 0) 
print(dist3s)

Submission status: Wrong Answer

Solution code:
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
seen = [0 for _ in range(n)]
clr = [2 for _ in range(n)]
seen[0] = 1
clr[0] = 0
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        now.append(y)
        clr[y] = 1 - clr[x]
#print(seen)
#print(clr)
a = sum(clr)
b = n - a
z1 = 1
z2 = 2
z3 = 3
g1 = (n+2)//3
g2 = (n+1)//3
g3 = n//3
ans = [0 for _ in range(n)]
if a > g3 and b > g3:
  for i in range(n):
    if clr[i] == 0:
      if g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z3
        z3 += 3
    else:
      if g2:
        ans[i] = z2
        z2 += 3
        g2 -= 1
      else:
        ans[i] = z3
        z3 += 3
elif a <= g3:
  g3 -= a
  for i in range(n):
    if clr[i] == 0:
      ans[i] = z3
      z3 += 3
    else:
      if g3:
        ans[i] = z3
        z3 += 3
        g3 -= 1
      elif g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z2
        z2 += 3
elif b <= g3:
  g3 -= b
  for i in range(n):
    if clr[i] == 1:
      ans[i] = z3
      z3 += 3
    else:
      if g3:
        ans[i] = z3
        z3 += 3
        g3 -= 1
      elif g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z2
        z2 += 3
else:
  err
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
g = [[N+1 for i in range(N)]for j in range(N)]
g = np.array(g)
for i in range(N-1):
  a,b = map(int,input().split())
  g[a-1][b-1] = 1
  g[b-1][a-1] = 1
print(g)
g_l = g
X = [0 for i in range(N)]
for k in range(N):
  for i in range(N):
    for j in range(i+1,N):
      g_l[i][j] = min(g_l[i][j], g_l[i][k] +g_l[k][j])
      if g_l[i][j] == 3:
        if(X[i] == 0):
          X[i] = 3
        else:
          aa = 1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

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

Q=[1]
COLOR[1]=1

while Q:
    x=Q.pop()
    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=1-COLOR[x]
            Q.append(to)

A1=N//3
A2=N//3
A3=N//3

if N%3==1:
    A1+=1
elif N%3==2:
    A1+=1
    A2+=1

S1=COLOR.count(1)
S2=COLOR.count(0)


SA=A1+A3-A2

if abs(S1-S2)>SA:
    print(-1)
    sys.exit()

ANS=[0]*(N+1)
now1=1
now2=2
if S1<S2:
    for i in range(1,N+1):
        if COLOR[i]==1:
            ANS[i]=now2
            now2+=3
        else:
            ANS[i]=now1
            now1+=3

else:
    for i in range(1,N+1):
        if COLOR[i]==0:
            ANS[i]=now2
            now2+=3
        else:
            ANS[i]=now1
            now1+=3

now3=3
for i in range(1,N+1):
    if ANS[i]>N:
        ANS[i]=now3
        now3+=3

print(*ANS[1:])

Submission status: Wrong Answer

Solution code:
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)


# Euler Tour の構築
S = []
F = [0]*N
depth = [0]*N
visited = set()

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


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

from collections import deque
q = deque([i for i in range(1,N+1) if i%3 == 0 ] + [i for i in range(1,N+1) if i%3 != 0 ])

if len(list(filter(lambda d: d%2 == 0, depth))) < N//2:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q.popleft()
    for i, d in enumerate(depth):
        if d%2 != 0:
            res[i] = q.popleft()


else:
    for i, d in enumerate(depth):
        if d%2 != 0:
            res[i] = q.popleft()
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q.popleft()


print_l(res)

Submission status: Wrong Answer

Solution code:
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


for i in range(M,-1,-1):
    if i%2==0:
        for p in x[i]:
            if tmp1<=n:
                ans[p]=tmp1
                tmp1+=3
            else:
                ans[p]=tmp3
                tmp3+=3
    else:
        for p in x[i]:
            if tmp2<=n:
                ans[p]=tmp2
                tmp2+=3
            else:
                ans[p]=tmp3
                tmp3+=3


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

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import copy
n = int(input())
lst = [[] for i in range(n)]
threelist = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    lst[a-1].append(b)
    lst[b-1].append(a)
print(lst)
for i in range(n):
    one = copy(lst[i])
    two = []
    for j in one:
        for k in lst[j-1]:
            if k != i+1:
                two.append(k)
    for j in two:
        for k in lst[j-1]:
            if not k in one:
                threelist[i].append(k)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def BFS(K, edges, N):
    roots = [[] for _ in range(N)]
    c = 1
    for a, b in edges:
        roots[a-1] += [(b-1, c)]
        roots[b-1] += [(a-1, c)]

    dist = [-1] * N
    stack = deque()
    stack.append(K)
    dist[K] = 0
    while stack:
        label = stack.pop()
        for i, c in roots[label]:
            if dist[i] == -1:
                dist[i] = dist[label] + c
                stack += [i]

    return dist


def main():
    N = INT()
    edges = [LIST() for i in range(N-1)]

    graph = [BFS(i, edges, N) for i in range(N)]
    
    ans = [1] * N
    for i in range(N-1):
        for j in range(i+1,N):
            if graph[i][j] == 3:
                ans[i] = 3
                ans[j] = 3

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[0]*n for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1][b-1]=1
  edge[b-1][a-1]=1

def distance3(s,edge):
  d=[0]*n
  queue=[s]
  used=[]
  cnt=0
  
  while 1:
    if len(queue)==0:
      break
    for i,x in enumerate(edge[queue[0]]):
      if x==1 and not(i in used):
        queue.append(i)
        d[i]+=1+d[queue[0]]
    used.append(queue[0])
    queue=queue[1:]
    cnt+=1
  return d

d=[]
l=[]
for i in range(n):
  d.append(distance3(i,edge))
for i in range(n):
  for j in range(i+1,n):
    if d[i][j]==3:
      l.append((i,j))
print(l)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

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

Q=[1]
COLOR[1]=1

while Q:
    x=Q.pop()
    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=1-COLOR[x]
            Q.append(to)

# UnionFind (min型. 一部のデータには危険)

Group=[i for i in range(N+1)]# グループ分け.Group[i]=jのときiとjは同じグループ

def find(x):# find(a)=find(b)のとき同じグループ
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  # xとyが同じグループになるよう更新
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))
            
def step3(now):
    USE=[0]*(N+1)
    USE[now]=1

    step_1=set()
    for to in E[now]:
        step_1.add(to)
        USE[to]=1

    step_2=set()
    for x in step_1:
        for to in E[x]:
            if USE[to]==0:
                USE[to]=1
                step_2.add(to)

    step_3=set()
    for x in step_2:
        for to in E[x]:
            if USE[to]==0:
                USE[to]=1
                step_3.add(to)

    for x in step_3:
        Union(now,x)

for i in range(1,N+1):
    if find(i)==i:
        step3(i)

A1=N//3
A2=N//3
A3=N//3

if N%3==1:
    A1+=1
elif N%3==2:
    A1+=1
    A2+=1

CS=[[0]*2 for i in range(N+1) ]
for i in range(1,N+1):
    CS[find(i)][COLOR[i]]+=1

INVI=[[] for i in range(N+1)]
for i in range(1,N+1):
    INVI[find(i)].append(i)

ANS=[0]*(N+1)
now1=1
now2=2
now3=3

for i in range(1,N+1):
    x=CS[i][0]
    y=CS[i][1]

    if x+y<=1:
        continue

    t3=(x+y)//3

    if x<=t3:
        for k in INVI[i]:
            if COLOR[k]==0:
                ANS[k]=now3
                now3+=3
            else:
                if now1<now2:
                    ANS[k]=now1
                    now1+=3
                else:
                    ANS[k]=now2
                    now2+=3

    elif y<=t3:
        for k in INVI[i]:
            if COLOR[k]==1:
                ANS[k]=now3
                now3+=3
            else:
                if now1<now2:
                    ANS[k]=now1
                    now1+=3
                else:
                    ANS[k]=now2
                    now2+=3
    else:
        for k in INVI[i]:
            if COLOR[k]==0:
                ANS[k]=now1
                now1+=3
            else:
                ANS[k]=now2
                now2+=3
                
for i in range(1,N+1):
    if ANS[i]==0:
        if now1<N:
            ANS[i]=now1
            now1+=3
        else:
            ANS[i]=now2
            now2+=3
for i in range(1,N+1):
    if ANS[i]>N:
        ANS[i]=now3
        now3+=3

print(*ANS[1:])

Submission status: Wrong Answer

Solution code:
from sys import exit
import sys
sys.setrecursionlimit(1000000000)

N = int(input())


class Node:
    def __init__(self, index):
        self.index = index
        self.paths = []
        self.num = -1


nodes = [Node(i) for i in range(N)]
one = [i for i in range(1, N+1, 3)]
two = [i for i in range(2, N+1, 3)]
three = [i for i in range(3, N+1, 3)]

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


def rec(node, key, passed):
    passed.add(node.index)
    if key == 1:
        if len(one) > 0:
            node.num = one.pop()
        elif len(three) > 0:
            node.num = three.pop()
        else:
            print(-1)
            exit()
    else: # key == -1
        if len(two) > 0:
            node.num = two.pop()
        elif len(three) > 0:
            node.num = three.pop()
        else:
            print(-1)
            exit()
    for path in node.paths:
        if path in passed:
            continue
        passed = rec(nodes[path], key*(-1), passed)
    return passed

_ = rec(nodes[0], 1, set())

ans = [node.num for node in nodes]
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

from collections import deque

def calc_dist(G, start):
    que = deque()
    dep = [-1]*n
    que.append((-1,start,0))
    while que:
        p,v,d = que.pop()
        dep[v]=d
        for to in G[v]:
            if to != p:
                que.append((v,to,d+1))
    return dep

dep0 = calc_dist(G,0)
m = max(dep0)
left = dep0.index(m)
dep1 = calc_dist(G,left)
m = max(dep1)
right = dep1.index(m)
dep2 = calc_dist(G, right)

x = sum(i%2==0 for i in dep1)
y = n - x
ok = set()
for i in range(n):
    ma = max(dep1[i], dep2[i])
    if ma < 3:
        if dep1[i]%2 == 0:
            x -= 1
        else:
            y -= 1
        ok.add(i)

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)

ans = [0]*n
if x<y:
    one, two = two, one
for i in range(n):
    if i in ok:
        continue
    if dep1[i]%2 == 0:
        if one:
            ans[i] = one.pop()
        elif three:
            ans[i] = three.pop()
        else:
            print(-1)
            exit()
    else:
        if two:
            ans[i] = two.pop()
        elif three:
            ans[i] = three.pop()
        else:
            print(-1)
            exit()
res = one+two+three
for i in ok:
    ans[i] = res.pop()

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from itertools import permutations
def main():
    N = int( input())
    E = [[] for _ in range(N)]
    AB = [ tuple( map( lambda x:int(x)-1, input().split())) for _ in range(N-1)]
    T = [0]*N
    for a, b in AB:
        E[a].append(b)
        E[b].append(a)
        T[a] += 1
        T[b] += 1
    d = deque()
    P = [-1]*N
    F = [[] for _ in range(6)]
    for i in range(N):
        if T[i] == 1:
            P[i] = 0
            F[0].append(i)
            d.append(i)
            break

    while d:
        v = d.popleft()
        n = P[v]
        for w in E[v]:
            if P[w] == -1:
                d.append(w)
                P[w] = (n+1)%6
                F[(n+1)%6].append(w)

    L = [ len(F[i]) for i in range(6)]
    check = True
    for q in permutations( range(3)):
        for i in range(8):
            p = [i%2, i//2%2, i//4%2]
            check = True
            count = [N//3, (N+2)//3, (N+1)//3]
            for l in range(3):
                j = q[l]
                if p[j] == 0:
                    s = 1
                    t = 2
                else:
                    s = 2
                    t = 1
            
                if count[s] > L[j]:
                    count[s] -= L[j]
                else:
                    c = L[j] - count[s]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c

                if count[t] > L[j+3]:
                    count[t] -= L[j+3]
                else:
                    c = L[j+3] - count[t]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c
            if check:
                break
        if check:
            break

    count = [N//3, (N+2)//3, (N+1)//3]
    ds = [deque([ i*3+3 for i in range(count[0])]),  deque([ i*3+1 for i in range(count[1])]),  deque([ i*3+2 for i in range(count[2])])]
    ANS = [0]*N
    for j in range(3):
        i = q[j]
        x = i
        y = i+3
        if p[i] == 0:
            s = 1
            t = 2
        else:
            s = 2
            t = 1
        for w in F[x]:
            if ds[s]:
                count[s] -= 1
                ANS[w] = ds[s].popleft()
            elif ds[0]:
                count[0] -= 1
                ANS[w] = ds[0].popleft()
            else:
                count[t] -= 1
                ANS[w] = ds[t].popleft()

        for w in F[y]:
            if ds[t]:
                count[t] -= 1
                ANS[w] = ds[t].popleft()
            elif ds[0]:
                count[0] -= 1
                ANS[w] = ds[0].popleft()
            else:
                count[s] -= 1
                ANS[w] = ds[s].popleft()

               
    print( " ".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()