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())

node = [[] for _ in range(N)]

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

# 頂点1からの距離が奇数:1、偶数:0
group = [False] * N
# 親ノードを格納する
parents = list(range(N))

# ノードの選択
for p, n in enumerate(node):
    # 子ノードの選択
    for c in n:
        # 親ノードも選択されるので、その場合は飛ばす
        if c != parents[p]:
            # 子ノードの親を自分にする
            parents[c] = p
            # 子ノードのグループを自分と逆に設定する
            group[c] = not group[p]

true_num = sum(map(int, group))
false_num = N - true_num
p = [0] * N
mod_0 = [int(i) for i in range(1,N+1) if i%3 == 0]
mod_1 = [int(i) for i in range(1,N+1) if i%3 == 1]
mod_2 = [int(i) for i in range(1,N+1) if i%3 == 2]

if true_num >= N/3 and false_num >= N/3:
    for i in range(N):
        if group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            if mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
elif false_num < N/3:
    for i in range(N):
        if group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            elif mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            p[i] = mod_0.pop(0)
elif true_num < N/3:
    for i in range(N):
        if not group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            elif mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            p[i] = mod_0.pop(0)

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

Submission status: Wrong Answer

Solution code:
N = int(input())

node = [[] for _ in range(N)]

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

# 頂点1からの距離が奇数:1、偶数:0
group = [False] * N
# 親ノードを格納する
parents = list(range(N))

# ノードの選択
for p, n in enumerate(node):
    # 子ノードの選択
    for c in n:
        # 親ノードも選択されるので、その場合は飛ばす
        if c != parents[p]:
            # 子ノードの親を自分にする
            parents[c] = p
            # 子ノードのグループを自分と逆に設定する
            group[c] = not group[p]

true_num = sum(map(int, group))
false_num = N - true_num
print(true_num, false_num)
p = [0] * N
mod_0 = [int(i) for i in range(1,N+1) if i%3 == 0]
mod_1 = [int(i) for i in range(1,N+1) if i%3 == 1]
mod_2 = [int(i) for i in range(1,N+1) if i%3 == 2]

if true_num >= N/3 and false_num >= N/3:
    for i in range(N):
        if group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            if mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
elif false_num < N/3:
    for i in range(N):
        if group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            elif mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            p[i] = mod_0.pop(0)
elif true_num < N/3:
    for i in range(N):
        if not group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            elif mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            p[i] = mod_0.pop(0)

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

Submission status: Wrong Answer

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

b = [[] for i in range(n)]
a1=[]
a2=[]
ans=[0]*n
for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)
    b[a[i][1]-1].append(a[i][0]-1)

import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)
        a1.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    if dis[y]%2==0:
                        a1.append(y)
                    else:
                        a2.append(y)
        return a1,a2
    return bfs()

tree(0)

j = 0
k = 0
if min(len(a1),len(a2))<=n//3:
    if len(a1)<=n//3:
        for i in range(1,n+1):
            if i<=len(a1)*3 and i%3==0 and j<=len(a1)-1:
                ans[a1[j]]=i
                j+=1
            else:
                ans[a2[k]]=i
                k+=1
    else:
        for i in range(1,n+1):
            if i<=len(a2)*3 and i%3==0 and j<=len(a2)-1:
                ans[a2[j]]=i
                j+=1
            else:
                ans[a1[k]]=i
                k+=1

else:
    for i in range(1,n+1):
        if (i%3==0 or i%3==1) and j<=len(a1)-1:
            ans[a1[j]]=i
            j+=1
        else:
            ans[a2[k]] = i
            k += 1

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)

def main():
    n=int(input())
    tree=[[] for i in range(n)]
    for _ in range(n-1):
       a,b=map(int,input().split())
       a-=1
       b-=1
       tree[a].append(b)
       tree[b].append(a)
    
    depth=[-1]*n
    depth[0]=0

    def dfs(i):
        for e in tree[i]:
            if depth[e]==-1:
                depth[e]=(depth[i]+1)%2
                dfs(e)
    dfs(0)
    o=sum(depth)
    e=n-o

    if n%3==0:
        i = n//3
        j = i
        k = i
    elif n%3==1:
        i = n//3
        j = i+1
        k = i
    else:
        i = n//3
        j = i+1
        k = j

    print(i,j,k)
    print(depth)
    print(e,o)

    ans=[0]*n
    if 3*e > n and 3*o > n:
        for l in range(n):
            if depth[l]==0:
                if j==0:
                    ans[l]=3*i
                    i-=1
                else:
                    ans[l]=3*j-2
                    j-=1
            else:
                if k==0:
                    ans[l]=3*i
                    i-=1
                else:
                    ans[l]=3*k-1
                    k-=1
    
    elif 3*e <= n:
        for l in range(n):
            if depth[l]==0:
                ans[l]=3*i
                i-=1
            else:
                if j==0 and k==0:
                    ans[l]=3*i
                    i-=1
                elif j==0:
                    ans[l]=3*k-1
                    k-=1
                else:
                    ans[l]=3*j-2
                    j-=1
    
    else:
        for l in range(n):
            if depth[l]==1:
                ans[l]=3*i
                i-=1
            else:
                if j==0 and k==0:
                    ans[l]=3*i
                    i-=1
                elif j==0:
                    ans[l]=3*k-1
                    k-=1
                else:
                    ans[l]=3*j-2
                    j-=1
    print(*ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
G = [[] for i in range(n)]

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


color = [-1]*n  # 木は二分グラフなので彩色

queue = deque([0])
color[0] = 0
red_blue = [1,0]  # 色毎に塗った数を記録

while queue:
    now = queue.popleft()
    for to in G[now]:
        if color[to] == -1:
            color[to] = 1 - color[now]
            red_blue[color[to]]+=1
            queue.append(to)

ans = [-1]*n  # 異なる色が塗られたもの同士の数字がmod3で同じにならなければ十分
if 3*red_blue[0] < n:
    red, blue = 3, 1
    for i in range(n):
        if color[i] == 0:
            ans[i] = red
            red += 3
        else:
            ans[i] = blue
            blue += 1
            if blue % 3 == 0: blue += 1
elif 3*red_blue[1] < n:
    red, blue = 1, 3
    for i in range(n):
        if color[i] == 1:
            ans[i] = blue
            blue += 3
        else:
            ans[i] = red
            red += 1
            if red % 3 == 0: red += 1
else:
    red,blue = 1,2
    three = 3
    for i in range(n):
        if color[i] == 0:
            if red <= n:
                ans[i] = red
                red += 3
            else:
                ans[i] = three
                three += 3
        else:
            if blue <= n:
                ans[i] = blue
                blue += 3
            else:
                ans[i] = three
                three += 3

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
G = [[] for i in range(n)]

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


color = [-1]*n  # 木は二分グラフなので彩色

queue = deque([0])
color[0] = 0
red_blue = [1,0]  # 色毎に塗った数を記録

while queue:
    now = queue.popleft()
    for to in G[now]:
        if color[to] == -1:
            color[to] = 1 - color[now]
            red_blue[color[to]]+=1
            queue.append(to)

ans = [-1]*n  # 異なる色が塗られたもの同士の数字がmod3で同じにならなければ十分
if 3*red_blue[0] <= n:
    red, blue = 3, 1
    for i in range(n):
        if color[i] == 0:
            ans[i] = red
            red += 3
        else:
            ans[i] = blue
            blue += 1
            if blue % 3 == 0: blue += 1
elif 3*red_blue[1] <= n:
    red, blue = 1, 3
    for i in range(n):
        if color[i] == 1:
            ans[i] = blue
            blue += 3
        else:
            ans[i] = red
            red += 1
            if red % 3 == 0: red += 1
else:
    red,blue = 1,2
    three = 3
    for i in range(n):
        if color[i] == 0:
            if red <= n:
                ans[i] = red
                red += 3
            else:
                ans[i] = three
                three += 3
        else:
            if blue <= n:
                ans[i] = blue
                blue += 3
            else:
                ans[i] = three
                three += 3

print(*ans)

Submission status: Wrong Answer

Solution code:
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
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
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 1:
    if len(A)>len(B):
        A,B=B,A
    
    qq=deque([i for i in range(1,n+1,3)]+[i for i in range(3,n+1,3)]+[i for i in range(2,n+1,3)])
    for i in A:
        ans[i]=qq.popleft()
    for i in B:
        ans[i]=qq.popleft()
            
    print(*ans)

Submission status: Wrong Answer

Solution code:
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
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
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 1:
    if len(A)>len(B):
        A,B=B,A
    qq=deque([i for i in range(1,n+1,3)]+[i for i in range(3,n+1,3)]+[i for i in range(2,n+1,3)])
    for i in A:
        ans[i]=qq.popleft()
    for i in B:
        ans[i]=qq.popleft()
            
    print(*ans)
    exit()

Submission status: Wrong Answer

Solution code:
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
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
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=deque([i for i in range(1,n+1,3)]+[i for i in range(3,n+1,3)]+[i for i in range(2,n+1,3)])
    for i in A:
        ans[i]=qq.popleft()
        
    
    for t in range(n):
        if ans[t]==0:
            ans[t]=qq.popleft()
            
    print(*ans)
    exit()
qq=deque([i for i in range(1,n+1,3)]+[i for i in range(3,n+1,3)]+[i for i in range(2,n+1,3)])
for i in A:
    ans[i]=qq.popleft()

for j in B:
    ans[j]=qq.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
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: len(to[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()

Submission status: Wrong Answer

Solution code:
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
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
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=deque([3*i+1 for i in range(int(n/3+0.9999))]+[3*i for i in range(int(n//3),0,-1)]+[3*i+2 for i in range(int(n/3+0.9999))])
    for i in A:
        ans[i]=qq.popleft()
        
    
    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)

Submission status: Wrong Answer

Solution code:
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
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
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)

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(2147483647)

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))

# vertice = [0 for _ in range(n)]
#
#
# def dfs(v, color_i):
#     vertice[v] = color_i
#     for i in edges[v]:
#         if vertice[i] == 0:
#             dfs(i, color_i*(-1))
#
# dfs(0, 1)

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()))
                continue
        if not3:
            ans.append(str(not3.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()))
                continue
        if not3:
            ans.append(str(not3.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))

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(2147483647)

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))

# vertice = [0 for _ in range(n)]
#
#
# def dfs(v, color_i):
#     vertice[v] = color_i
#     for i in edges[v]:
#         if vertice[i] == 0:
#             dfs(i, color_i*(-1))
#
# dfs(0, 1)

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()))
                continue
        if not3:
            ans.append(str(not3.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()))
                continue
        if not3:
            ans.append(str(not3.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()))
            elif num3:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            elif num3:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
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)//N + 1:
            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)//N + 1:
            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

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

Submission status: Wrong Answer

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

# 1 index
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 d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

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

print()

Submission status: Wrong Answer

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

# 1 index
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:
            if mod2:
                node_p[i] = mod2.pop()
            elif mod0:
                node_p[i] = mod0.pop()

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


odd = 0
even = 0

bfs(N)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

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

print()

Submission status: Wrong Answer

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

# 1 index
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:
            if mod2:
                node_p[i] = mod2.pop()
            elif mod0:
                node_p[i] = mod0.pop()

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


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

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

print()

Submission status: Wrong Answer

Solution code:
print("3 "*int(input()))