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:
n=int(input())
ki=[[] for _ in range(n)]

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

odd=[-1]*n
odd[0]=0
todo=[0]
while todo:
    v=todo.pop()
    for nv in ki[v]:
        if odd[nv]==-1:
            odd[nv]=abs(odd[v]-1)
            todo.append(nv)
from collections import Counter
co=Counter(odd)
ans=[0]*n
if co[1]<n//3:
    cnt1=1
    cnt2=2
    cnt3=1
    for i in range(n):
        if odd[i]==1 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1

elif co[0]<n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==0 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1
else:
    cnt1=1
    cnt2=1
    cnt3=1
    for i in range(n):
        if odd[i]==1:
            if 3*cnt1-2<=n:
                ans[i]=3*cnt1-2
                cnt1+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
        else:
            if 3*cnt2-1<=n:
                ans[i]=3*cnt2-1
                cnt2+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
print(*ans,sep=' ')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n = int(input())
    tree = [[] for _ 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)
    
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    dist = [0]*n

    while not_yet:
        value = not_yet.popleft()
        for v in tree[value]:
            if already[v]:
                continue
            already[v] = True
            dist[v] = (dist[value] + 1) % 2
            not_yet.append(v)
    
    zero = dist.count(0)
    one = dist.count(1)

    ans = [0]*n
    already = [False]*n
    if zero >= one:
        if one <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 1:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            print(z, o)
            for i in range(n):
                if dist[i] == 0:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1
    else:
        if zero <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 0:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 1:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1

    print(*ans)

            



    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n = int(input())
    tree = [[] for _ 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)
    
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    dist = [0]*n

    while not_yet:
        value = not_yet.popleft()
        for v in tree[value]:
            if already[v]:
                continue
            already[v] = True
            dist[v] = (dist[value] + 1) % 2
            not_yet.append(v)
    
    zero = dist.count(0)
    one = dist.count(1)

    ans = [0]*n
    already = [False]*n
    if zero >= one:
        if one <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 1:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 0:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1
    else:
        if zero <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 0:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 1:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1

    print(*ans)

            



    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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)
LAST=[0]*n
now1=1
now2=2
for i in range(n):
    if dist[i]==0:
        LAST[i]=now1
        now1= now1+3 if now1<n-2 else 0
    else:
        LAST[i]=now2
        now2= now2+3 if now2<n-2 else 0

now3=3
for i in range(n):
    if LAST[i]==0:
        LAST[i]=now3
        now3+=3
print(*LAST)

Submission status: Wrong Answer

Solution code:
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)
LAST=[0]*n
now1=1
now2=2
for i in range(n):
    if dist[i]==0:
        LAST[i]=now1
        now1= now1+3 if now1<=n-2 else 0
    else:
        LAST[i]=now2
        now2= now2+3 if now2<=n-2 else 0

now3=3
for i in range(n):
    if LAST[i]==0:
        LAST[i]=now3
        now3+=3
print(*LAST)

Submission status: Wrong Answer

Solution code:
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)
LAST=[0]*n
now1=1
now2=2
for i in range(n):
    if dist[i]==0:
        LAST[i]=now1
        now1= now1+3 if now1<=n-2 else 0
    else:
        LAST[i]=now2
        now2= now2+3 if now2<=n-2 else 0

now3=3
for i in range(n):
    if LAST[i]==0:
        LAST[i]=now3
        now3+=3
print(LAST)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
N=int(input())

tree=[[] for _ in range(N+1)]
occur_list=[0]*(N+1)
for _ in range(N-1):
  a,b=map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  occur_list[a]+=1
  occur_list[b]+=1
#print(tree)
#print(occur_list)

leaf=0
for i in range(1,N+1):
  if occur_list[i]==1:
    leaf=i
    break
#print(leaf)

def dfs(u,p1,p2,p3):
  global min_3m0
  global min_3m1
  global min_3m2
  
  if p3==0:
    if min_3m1<=N:
      mark_list[u]=min_3m1
      min_3m1+=3
    elif min_3m2<=N:
      mark_list[u]=min_3m2
      min_3m2+=3
    elif min_3m0<=N:
      mark_list[u]=min_3m0
      min_3m0+=3
    else:
      print(-1)
      sys.exit(0)
  elif mark_list[p3]%3==0:
    if min_3m1<=N:
      mark_list[u]=min_3m1
      min_3m1+=3
    elif min_3m2<=N:
      mark_list[u]=min_3m2
      min_3m2+=3
    elif min_3m0<=N:
      mark_list[u]=min_3m0
      min_3m0+=3
    else:
      print(-1)
      sys.exit(0)
  elif mark_list[p3]%3==1:
    if min_3m2<=N:
      mark_list[u]=min_3m2
      min_3m2+=3
    elif min_3m0<=N:
      mark_list[u]=min_3m0
      min_3m0+=3
    else:
      print(-1)
      sys.exit(0)
  elif mark_list[p3]%3==2:
    if min_3m1<=N:
      mark_list[u]=min_3m1
      min_3m1+=3
    elif min_3m0<=N:
      mark_list[u]=min_3m0
      min_3m0+=3
    else:
      print(-1)
      sys.exit(0)
    
  for v in tree[u]:
    if mark_list[v]==0:
      dfs(v,u,p1,p2)

mark_list=[0]*(N+1)
min_3m0=3
min_3m1=1
min_3m2=2
dfs(leaf,0,0,0)

print(*mark_list[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
N=int(input())

tree=[[] for _ in range(N+1)]
occur_list=[0]*(N+1)
for _ in range(N-1):
  a,b=map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  occur_list[a]+=1
  occur_list[b]+=1
#print(tree)
#print(occur_list)

leaf=0
for i in range(1,N+1):
  if occur_list[i]==1:
    leaf=i
    break
#print(leaf)

def dfs(u,p1,p2,p3):
  global min_3m0
  global min_3m1
  global min_3m2
  
  if p3==0:
    if min_3m0<=N:
      mark_list[u]=min_3m0
      min_3m0+=3
    elif min_3m1<=N:
      mark_list[u]=min_3m1
      min_3m1+=3
    elif min_3m2<=N:
      mark_list[u]=min_3m2
      min_3m2+=3
    else:
      print(-1)
      sys.exit(0)
  elif mark_list[p3]%3==0:
    if min_3m1<=N:
      mark_list[u]=min_3m1
      min_3m1+=3
    elif min_3m2<=N:
      mark_list[u]=min_3m2
      min_3m2+=3
    elif min_3m0<=N:
      mark_list[u]=min_3m0
      min_3m0+=3
    else:
      print(-1)
      sys.exit(0)
  elif mark_list[p3]%3==1:
    if min_3m2<=N:
      mark_list[u]=min_3m2
      min_3m2+=3
    elif min_3m0<=N:
      mark_list[u]=min_3m0
      min_3m0+=3
    else:
      print(-1)
      sys.exit(0)
  elif mark_list[p3]%3==2:
    if min_3m1<=N:
      mark_list[u]=min_3m1
      min_3m1+=3
    elif min_3m0<=N:
      mark_list[u]=min_3m0
      min_3m0+=3
    else:
      print(-1)
      sys.exit(0)
    
  for v in tree[u]:
    if mark_list[v]==0:
      dfs(v,u,p1,p2)

mark_list=[0]*(N+1)
min_3m0=3
min_3m1=1
min_3m2=2
dfs(leaf,0,0,0)

print(*mark_list[1:])

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
for _ in range(N):
    print(3, end=' ')

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = numpy.ones(N) * -1
color[0] = 0

edges = []

for i in range(N - 1):
    root, tip = map(int, input().split())
    edges.append([root, tip])

edges = numpy.sort(numpy.array(edges))

for e in edges:
    root, tip = e[0], e[1]
    color[tip - 1] = 1 - color[root - 1]

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1 ,3)

d1 = numpy.where(color == 0)[0]
d2 = numpy.where(color == 1)[0]

if len(d1) <= N / 3:
    l = numpy.hstack([l3, l1, l2])

elif len(d2) <= N / 3:
    l = numpy.hstack([l1, l2, l3])

else:
    l = numpy.hstack([l2, l3, l1])

d = numpy.hstack([d1, d2])
print(' '.join(map(str, l[numpy.argsort(d)])))

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = numpy.ones(N) * -1
color[0] = 0

for i in range(N - 1):
    root, tip = map(int, input().split())
    color[tip - 1] = 1 - color[root - 1]

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1 ,3)

d1 = numpy.where(color == 0)[0]
d2 = numpy.where(color == 1)[0]

if len(d1) <= N / 3:
    l = numpy.hstack([l3, l1, l2])

elif len(d2) <= N / 3:
    l = numpy.hstack([l1, l2, l3])

else:
    l = numpy.hstack([l2, l3, l1])

d = numpy.hstack([d1, d2])
print(' '.join(map(str, l[numpy.argsort(d)])))

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = numpy.ones(N) * -1
color[0] = 0

for i in range(N - 1):
    root, tip = map(int, input().split())
    color[tip - 1] = 1 - color[root - 1]

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1 ,3)

d1 = numpy.where(color == 0)
d2 = numpy.where(color == 1)

if len(d1) < N / 3:
    l = numpy.hstack([l3, l1, l2])

elif len(d2) < N / 3:
    l = numpy.hstack([l1, l2, l3])

else:
    l = numpy.hstack([l2, l3, l1])

d = numpy.hstack([d1, d2])[0]
print(' '.join(map(str, l[d])))

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = numpy.ones(N) * -1
color[0] = 0

for i in range(N - 1):
    root, tip = map(int, input().split())
    color[tip - 1] = 1 - color[root - 1]

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1 ,3)

d1 = numpy.where(color == 0)
d2 = numpy.where(color == 1)

if len(d1) < N / 3:
    l = numpy.hstack([l1, l2, l3])

elif len(d2) < N / 3:
    l = numpy.hstack([l3, l1, l2])

else:
    l = numpy.hstack([l2, l3, l1])

s = map(str, l[numpy.argsort(color)])
print(' '.join(s))

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = numpy.ones(N) * -1
color[0] = 0

for i in range(N - 1):
    root, tip = map(int, input().split())
    color[tip - 1] = 1 - color[root - 1]

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1 ,3)

d1 = numpy.where(color == 0)
d2 = numpy.where(color == 1)

if N / 3 < len(d1) and N / 3 < len(d2):
    l = numpy.hstack([l2, l3, l1])

elif len(d1) < N / 3:
    l = numpy.hstack([l3, l1, l2])

else:
    l = numpy.hstack([l1, l2, l3])

s = map(str, l[numpy.argsort(color)])
print(' '.join(s))

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = numpy.ones(N) * -1
color[0] = 0

for i in range(N - 1):
    root, tip = map(int, input().split())
    color[tip - 1] = 1 - color[root - 1]

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1 ,3)

if numpy.count_nonzero(color == 0) <= N / 3:

    l = numpy.hstack([l3, l1, l2])

elif numpy.count_nonzero(color == 0) <= 2 * N / 3:

    l = numpy.hstack([l2, l3, l1])

else:

    l = numpy.hstack([l1, l2, l3])

s = map(str, l[numpy.argsort(color)])
print(' '.join(s))

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = numpy.ones(N) * -1
color[0] = 0

for i in range(N - 1):
    root, tip = map(int, input().split())
    color[tip - 1] = 1 - color[root - 1]

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1 ,3)

if numpy.count_nonzero(color == 0) <= N / 3:
    l = numpy.hstack([l3, l1, l2])

elif numpy.count_nonzero(color == 0) <= 2 * N / 3:
    l = numpy.hstack([l1, l3, l2])

else:
    l = numpy.hstack([l1, l2, l3])

s = map(str, l[numpy.argsort(color)])
print(' '.join(s))

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = [-1] * N
color[0] = 0
p = [-1] * N

for i in range(N - 1):
    root, tip = map(int, input().split())
    color[tip - 1] = 1 - color[root - 1]

color = numpy.array(color)

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1,3)

if numpy.count_nonzero(color == 0) <= N / 3:
    l = numpy.hstack([l3, l1, l2])

elif numpy.count_nonzero(color == 0) <= 2 * N / 3:
    l = numpy.hstack([l1, l3, l2])

else:
    l = numpy.hstack([l1, l2, l3])

print(l[numpy.argsort(color)])

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = [-1] * N
color[0] = 0
p = [-1] * N

for i in range(N - 1):
    root, tip = map(int, input().split())
    color[tip - 1] = 1 - color[root - 1]

color = numpy.array(color)

l1 = numpy.arange(1, N + 1 ,3)
l2 = numpy.arange(2, N + 1 ,3)
l3 = numpy.arange(3, N + 1,3)

if len(color[color == 0]) < N / 3:
    l = numpy.hstack([l3, l1, l2])

elif len(color[color == 1]) < N / 3:
    l = numpy.hstack([l1, l2, l3])

else:
    l = numpy.hstack([l1, l3, l2])

print(l[numpy.argsort(color)])

Submission status: Wrong Answer

Solution code:
import numpy

N = int(input())
color = [-1] * N
color[0] = 0 
# Blue -> 0, even number
# Red -> 1, odd number

edges = []

for i in range(N - 1):
    root, tip = map(int, input().split())
    edges.append([root, tip])

edges = numpy.sort(numpy.array(edges))

for e in edges:
    root, tip = e[0], e[1]
    color[tip - 1] = 1 - color[root - 1]
    
nodes = numpy.array(color).argsort() + 1

l1 = numpy.arange(1, N + 1, 3)
l2 = numpy.arange(2, N + 1, 3)
l3 = numpy.arange(3, N + 1, 3)

# blue less than N / 3, blue
if numpy.sum(color) < N / 3:
    l = numpy.hstack([l3, l1, l2])
# blue more then 2 * N / 3
elif 2 * N / 3 < numpy.sum(color):
    l = numpy.hstack([l1, l2, l3])
else:
    l = numpy.hstack([l2, l3, l1])

data = map(str, l[nodes - 1])
print(' '.join(data))

Submission status: Wrong Answer

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

rb = [-1]*n
rb[0] = 1
count1 = 1
count2 = 0
rb_m = [[0]]
for i in rb_m:
    n_rb = []
    for j in i:
        x = rb[j]
        for k in ab[j]:
            if(rb[k] != -1):
                continue
            if(x == 1):
                rb[k] = 2
                count2 += 1
            elif(x == 2):
                rb[k] = 1
                count1 += 1
            n_rb.append(k)
    set(n_rb)
    if(n_rb == []):
        break
    else:
        rb_m.append(n_rb)

ans = [0 for i in range(n)]
if(count1 >= n//3 and count2 >= n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 1 and ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(rb[i] == 2 and ne2 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
elif(count1 < n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 1):
            ans[i] = ne3
            ne3 += 3
        elif(ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(ne1 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
elif(count2 < n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 2):
            ans[i] = ne3
            ne3 += 3
        elif(ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(ne1 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

bigraph = [0] * n


def dfs(v, v_p, depth):
    bigraph[v] = depth % 2
    for v_next in graph[v]:
        if v_next == v_p:
            continue
        dfs(v_next, v, depth + 1)


dfs(0, -1, 1)
m1 = sum(bigraph)
m2 = n - m1

ans = [-1] * n
if m1 >= n // 3 + 1 and m2 >= n // 3 + 1:
    c1 = 1
    c2 = 2
    for i in range(n):
        if bigraph[i] == 0 and c1 <= n:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 1 and c2 <= n:
            ans[i] = c2
            c2 += 3
    c3 = 3
    for i in range(n):
        if ans[i] == -1:
            if c1 <= n:
                ans[i] = c1
                c1 += 3
            elif c2 <= n:
                ans[i] = c2
                c2 += 3
            else:
                ans[i] = c3
                c3 += 3
elif m1 > m2:
    # print('A')
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 0:
            # print(i, c1)
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 1 and c2 <= n:
            ans[i] = c2
            c2 += 3
    for i in range(n):
        if ans[i] == -1 and c1 <= n:
            ans[i] = c1
            c1 += 3
    for i in range(n):
        if ans[i] == -1 and c3 <= n:
            ans[i] = c3
            c3 += 3
else:  # m1 < m2
    # print('B')
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 1:
            # print(i, c1)
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 0 and c2 <= n:
            ans[i] = c2
            c2 += 3
    for i in range(n):
        if ans[i] == -1 and c1 <= n:
            ans[i] = c1
            c1 += 3
    for i in range(n):
        if ans[i] == -1 and c3 <= n:
            ans[i] = c3
            c3 += 3

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

bigraph = [0] * n


def dfs(v, v_p, depth):
    bigraph[v] = depth % 2
    for v_next in graph[v]:
        if v_next == v_p:
            continue
        dfs(v_next, v, depth + 1)


dfs(0, -1, 0)
m1 = sum(bigraph)
m2 = n - m1

ans = [-1] * n
if m1 >= n // 3 and m2 >= n // 3:
    c1 = 1
    c2 = 2
    for i in range(n):
        if bigraph[i] == 0 and c1 <= n:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 1 and c2 <= n:
            ans[i] = c2
            c2 += 3
    c3 = 3
    for i in range(n):
        if ans[i] == -1:
            if c1 <= n:
                ans[i] = c1
                c1 += 3
            elif c2 <= n:
                ans[i] = c2
                c2 += 3
            else:
                ans[i] = c3
                c3 += 3
elif m1 > m2:
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 0:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 1 and c2 <= n:
            ans[i] = c2
            c2 += 3
    for i in range(n):
        if ans[i] == -1 and c1 <= n:
            ans[i] = c1
            c1 += 3
    for i in range(n):
        if ans[i] == -1 and c3 <= n:
            ans[i] = c3
            c3 += 3
else:  # m1 < m2
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 1:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 0 and c2 <= n:
            ans[i] = c2
            c2 += 3
    for i in range(n):
        if ans[i] == -1 and c1 <= n:
            ans[i] = c1
            c1 += 3
    for i in range(n):
        if ans[i] == -1 and c3 <= n:
            ans[i] = c3
            c3 += 3

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

bigraph = [0] * n


def dfs(v, v_p, depth):
    bigraph[v] = depth % 2
    for v_next in graph[v]:
        if v_next == v_p:
            continue
        dfs(v_next, v, depth + 1)


dfs(0, -1, 0)
m1 = sum(bigraph)
m2 = n - m1

ans = [-1] * n
if m1 >= n // 3 and m2 >= n // 3:
    c1 = 1
    c2 = 2
    for i in range(n):
        if bigraph[i] == 0 and c1 <= n:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 1 and c2 <= n:
            ans[i] = c2
            c2 += 3
    c3 = 3
    for i in range(n):
        if ans[i] == -1:
            ans[i] = c3
            c3 += 3
elif m1 > m2:
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 0:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 1 and c2 <= n:
            ans[i] = c2
            c2 += 3
    for i in range(n):
        if ans[i] == -1 and c1 <= n:
            ans[i] = c1
            c1 += 3
    for i in range(n):
        if ans[i] == -1 and c3 <= n:
            ans[i] = c3
            c3 += 3
else:  # m1 < m2
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 1:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 0 and c2 <= n:
            ans[i] = c2
            c2 += 3
    for i in range(n):
        if ans[i] == -1 and c1 <= n:
            ans[i] = c1
            c1 += 3
    for i in range(n):
        if ans[i] == -1 and c3 <= n:
            ans[i] = c3
            c3 += 3

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
mod_0 = []
mod_1 = []
mod_2 = []
for i in range(1, n + 1):
    if i % 3 == 0:
        mod_0.append(i)
    elif i % 3 == 1:
        mod_1.append(i)
    else:
        mod_2.append(i)
ans = [-1]*n
from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

d = bfs(0)

cnt = [[] for _ in range(2)]

for i in range(n):
    if d[i] % 2 == 0:
        cnt[0].append(i + 1)
    elif d[i] % 2 == 1:
        cnt[1].append(i + 1)

cnt = sorted(cnt, key=lambda x: len(x))

for i in range(2):
    c = cnt[i]
    for j in range(len(c)):
        if mod_2 and i == 0:
            ans[cnt[i][j] - 1] = mod_2.pop()
        elif mod_1 and i == 1:
            ans[cnt[i][j] - 1] = mod_1.pop()
        elif mod_0:
            ans[cnt[i][j] - 1] = mod_0.pop()
        else:
            print(-1)
            sys.exit()
print(*ans)

Submission status: Wrong Answer

Solution code:
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())
  a=a-1
  b=b-1
  E[a].append(b)
  E[b].append(a)
D=deque([0])
V=[0]*n
V[0]=1
A=[0]*n
k=1
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(E[x])):
    if V[E[x][i]]==0:
      V[E[x][i]]=1
      D.append(E[x][i])
      A[E[x][i]]=A[x]^1
f=0
if n-sum(A)>sum(A):
  f=1
g=max(n-sum(A),sum(A))
a=(n+2)//3
b=n//3
if g>a+b:
  print(-1)
else:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==1:
    for i in range(n):
      if A[i]==0 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==0 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==1 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
  else:
    for i in range(n):
      if A[i]==1 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==1 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==0 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
  print(*Ans)