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:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    Par = [0 for _ in range(N)]
    Son = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    Dist = [0] * N
    q = deque()
    q.append((0, 0, 0)) #(now, pre, dist)
    modCount = [N // 3, N // 3, N // 3]
    if N % 3 == 1: modCount[1] += 1
    elif N % 3 == 2:
        modCount[1] += 1
        modCount[2] += 1
    modIndex = [0, 0, 0]
    search = deque()
    while q:
        nowNode, preNode, dist = q.popleft()
        Dist[nowNode] = dist
        Par[nowNode] = preNode
        Son[preNode].append(nowNode)
        search.append(nowNode)
        for nextNode in Edge[nowNode]:
            if nextNode != preNode: q.append((nextNode, nowNode, dist + 1))
        
    Safe = [True] * N
    Ans = [-1] * N
    Check = False
    while search:
        nowNode = search.popleft()
        dType = Dist[nowNode] % 2
        if modIndex[dType + 1] < modCount[dType + 1]: 
            Ans[nowNode] = 3 * modIndex[dType + 1] + dType + 1
            modIndex[dType + 1] += 1

        elif modIndex[0] < modCount[0]:
            Ans[nowNode] = 3 * modIndex[0] + 3
            modIndex[0] += 1

        else:
            if Dist[nowNode] < 2:
                Ans[nowNode] = 3 * modIndex[(dType ^ 1) + 1] + (dType ^ 1) + 1
                modIndex[(dType ^ 1) + 1] += 1
                Safe[nowNode] = False
                Check = True
            else:
                f = Par[nowNode]
                g = Par[f]
                print(f, g)
                if not Safe[g]:
                    print(-1)
                    break
                else:
                    possible = True
                    for u in Son[g]:
                        if u != f and not Safe[u]:
                            possible = False
                            break
                    if possible:
                        Ans[nowNode] = 3 * modIndex[(dType ^ 1) + 1] + (dType ^ 1) + 1
                        modIndex[(dType ^ 1) + 1] += 1
                        Safe[nowNode] = False
                        Check = True
                    else:
                        print(-1)
                        break
            for son in Edge[Par[nowNode]]:
                if son != Par[nowNode] and len(Son[son]) > 0:
                    print(-1)
                    break
    else:
        print(" ".join(map(str, Ans)))


    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

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

grand_sum = [0 for _ in range(n)]
for i in range(n):
	grand_sum[i] = sum([len(adj[x]) for x in adj[i]]) - len(adj[i])

if n <= 3:
	print(*list(range(1, n+1)))
	sys.exit()

ans = [-1 for _ in range(n)]
#ONE, TWO = n//3 + (n%3 > 0), n//3 + (n%3 > 1)

tri = [0 for _ in range(n)]
for a, b in edges:
	tri[b] += grand_sum[a] - len(adj[b]) + 1
	tri[a] += grand_sum[b] - len(adj[a]) + 1
	#print(a, b)
	#print(tri_a, tri_b)
	#print("---")
#print(tri)

#THREE = 3
#for i, t in enumerate(tri):
#	if t >= n - (n//3):
#		if THREE > n:
#			print(-1)
#			sys.exit()
#		ans[i] = THREE
#		THREE += 3

flg = False
orig = -1
for i, t in enumerate(tri):
	if t >= n - (n//3):
		flg = True
		orig = i

#parity = [0, 0]
signs = [-1 for _ in range(n)]
def dfs(x):
	for v in adj[x]:
		if signs[v] < 0:
			signs[v] = 1 ^ signs[x]
			dfs(v)

signs[0] = 0
dfs(0)

if flg:
	cur = [1, 2, 3]
	for i in range(n):
		if signs[i] == signs[orig]:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] <= n:
			ans[i] = cur[0]
			cur[0] += 3
		elif cur[1] <= n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[2]
			cur[2] += 3
	print(*ans)
	sys.exit()

num1 = sum(signs)
num2 = n - num1

#print(signs)

M, m = max(num1, num2), min(num1, num2) 

if max(num1, num2) >= n - (n // 3):
	if num1 > num2:
		more = 1
	else:
		more = 0
	cur = [1, 2, 3]
	for i in range(n):
		if signs[i] == more:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] <= n:
			ans[i] = cur[0]
			cur[0] += 3
		elif cur[1] <= n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[2]
			cur[2] += 3
	print(*ans)
	sys.exit()

#	print(-1)
#	sys.exit()
#else:
if num1 > num2:
	one, two = num1, num2
	more = 1
else:
	one, two = num2, num1
	more = 0
cur = [2, 1, 3]
for i in range(n):
	if ans[i] > 0:
		continue
	if signs[i] == more:
		if cur[1] > n and cur[2] <= n: 
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[1] > n and cur[2] > n:
			ans[i] = cur[0]
			cur[0] += 3
		else:
			ans[i] = cur[1]
			cur[1] += 3
	else:
		if cur[0] > n and cur[2] <= n:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] > n and cur[2] > n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[0]
			cur[0] += 3
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
    pp = [0,0,0]
    qq = [0,1,2]
    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:
                pp = p
                qq = q
                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 = qq[j]
        x = i
        y = i+3
        if pp[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()

Submission status: Wrong Answer

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

def main():
    n=int(input())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    Depth=[-1]*n
    Depth[0]=0
    q=deque()
    q.append(0)
    while q:
        fr=q.popleft()
        for to in Edges[fr]:
            if Depth[to]==-1:
                Depth[to]=Depth[fr]+1
                q.append(to)
    Group=[[] for _ in range(2)]
    for i in range(n):
        Group[Depth[i]%2].append(i)
    #print(Depth,Group)
    l_even,l_odd=len(Group[0]),len(Group[1])
    #print(l_even,l_odd)
    Ans=[0]*n
    Used=[False]*(n+1)
    if l_even<=l_odd:
        if l_even<n//3:
            tmp_3=3
            tmp_others=1
            for i in range(n):
                if Depth[i]%2==0:
                    Ans[i]=tmp_3
                    Used[tmp_3]=True
                    tmp_3+=3
                else:
                    while Used[tmp_others]:
                        tmp_others+=1
                    Ans[i]=tmp_others
                    Used[tmp_others]=True
            print(*Ans)
            exit()
    else:
        if l_odd<n//3:
            tmp_3=3
            tmp_others=1
            for i in range(n):
                if Depth[i]%2==1:
                    Ans[i]=tmp_3
                    Used[tmp_3]=True
                    tmp_3+=3
                else:
                    while Used[tmp_others]:
                        tmp_others+=1
                    Ans[i]=tmp_others
                    Used[tmp_others]=True
            print(*Ans)
            exit()
    tmp_odd,tmp_even,tmp_others=1,2,3
    for i in range(n):
        #print(Depth[i])
        if Depth[i]%2==1:
            if tmp_odd<=n:
                #print('A')
                Ans[i]=tmp_odd
                tmp_odd+=3
            else:
                #print('B')
                Ans[i]=tmp_others
                tmp_others+=3
        else:
            if tmp_even<=n:
                #print('C')
                Ans[i]=tmp_even
                tmp_even+=3
            else:
                #print('D')
                Ans[i]=tmp_others
                tmp_others+=3
    print(*Ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def warshall_floyd(d,n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def main():
    n=int(input())
    d = [[float("inf")]*n for i in range(n)] 
    #d[u][v] : 辺uvのコスト(存在しないときはinf)
    for _ in range(n-1):
        x,y = map(int,input().split())
        d[x-1][y-1] = 1
        d[y-1][x-1] = 1
    for i in range(n):
        d[i][i] = 0 #自身のところに行くコストは０
    warshall_floyd(d,n)
    
    L=[]
    for i in range(n):
        for j in range(i,n):
            if d[i][j]==3:
                L.append([i+1,j+1])
    cand=list(set([i for i,j in L] + [j for i,j in L]))
    
    # candのindexに変換
    for l in L:
        l[0] = cand.index(l[0])
        l[1] = cand.index(l[1])
    ans=[0]*n
    for C in combinations([i for i in range(1,n+1)],len(cand)):
        for l in L:
            if C[l[0]]%3==C[l[1]]%3>0:
                break
        else:
            for ca, c in zip(cand,C):
                ans[ca-1] = c
            b=1
            for i in range(1,n+1):
                if ans[i-1] == 0:
                    while b in C:
                        b += 1
                    ans[i-1]=b 
                    b += 1
            print(*ans)
            return
    print(-1)
main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import queue

def main():
    N=I()
    adj=[[] for _ in range(N)]
    mod1=range(1,N+1,3)
    n1=0
    mod2=range(2,N+1,3)
    n2=0
    mod3=range(3,N+1,3)
    n3=0
    
    p=[0]*N
    
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
     
    
    q=queue.Queue()
    q.put((0,-1,0))#node,par,depth
    d=[0]*N#深さをメモ
            
        
    while not q.empty():
        v,par,depth=q.get()
        d[v]=depth%2
                
        for i in range(len(adj[v])):
            nxt=adj[v][i]
            if nxt!=par:
                q.put((nxt,v,depth+1))
                
    dmod=[0,0]
    for i in range(N):
        dmod[d[i]]+=1
        
    for i in range(N):
        bit=d[i]
        if dmod[bit]<dmod[(bit+1)%2]:
            if n3<len(mod3):
                p[i]=mod3[n3]
                n3+=1
            elif bit==1:
                if n1<len(mod1):
                    p[i]=mod1[n1]
                    n1+=1
                else:
                    p[i]=mod2[n2]
                    n2+=1
            else:
                if n2<len(mod2):
                    p[i]=mod2[n2]
                    n2+=1
                else:
                    p[i]=mod1[n1]
                    n1+=1
                
        else:
            if bit==1:
                if n1<len(mod1):
                    p[i]=mod1[n1]
                    n1+=1
                elif n3<len(mod3):
                    p[i]=mod3[n3]
                    n3+=1
                else:
                    p[i]=mod2[n2]
                    n2+=1
            else:
                if n2<len(mod2):
                    p[i]=mod2[n2]
                    n2+=1
                elif n3<len(mod3):
                    p[i]=mod3[n3]
                    n3+=1
                else:
                    p[i]=mod1[n1]
                    n1+=1
        dmod[bit]-=1
            
        
                    
                
    
                
    print(' '.join(map(str, p)))
        
        
    
    
        
                
            
        
        
    

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class Graph():
    def __init__(self,vertex_num,node_num,naive_input,start_zero=True,direction=False,weight=True):
        self.vertex_num=vertex_num
        self.node_num=node_num
        #nodeには入力時のインデックスも含む
        #[接続ノード , インッデクス]のarray
        node=[{} for _ in range(vertex_num)]
        for i in range(node_num):
            if weight:
                u,v,w=naive_input[i]
            else:
                u,v=naive_input[i]
                w=1
            if not start_zero:
                u-=1
                v-=1
            node[u][v]={"weight":w,"index":i}
            #node[v][u]={"weight":w,"index":i}
            if not direction:
                node[v][u]={"weight":w,"index":i}
                #node[u][v]["reverse"]={"weight":w,"index":i}
        self.node=node
        #それぞれの頂点の辺の数
        self.node_num_arr=list(map(lambda x:len(x),node))
        self.parent=[-1 for _ in range(self.vertex_num)]
        self.three=[set() for _ in range(self.vertex_num)]

    #頂点nowから順にbfs
    #頂点nowから順にbfs
    def bfs(self,s=0):
        def cal_distance(now_edge,next_edge,distance_arr):
            distance_arr[next_edge]=distance_arr[now_edge]+1

        def append_shinseki(now_edge,next_edge):
            p=self.parent[now_edge]
            p_child=set(self.node[p].keys())
            #print(self.parent)
            #print("parent:",p)
            #print("now;",now_edge,"next",next_edge)
            #print(p_child)
            p_child.remove(now_edge)
            self.three[next_edge]=p_child
        #bfs用のキュー
        q=[-1 for _ in range(self.vertex_num)]
        #pypyを使うときは要変更
        cal_node_num_arr=self.node_num_arr.copy()
        now_ind=0
        q[now_ind]=s
        last_ind=1


        distance=[0 for _ in range(self.vertex_num)]




        while last_ind<self.vertex_num:
            now_edge=q[now_ind]
            if cal_node_num_arr[now_edge]<=0:
                now_ind+=1
                continue
            for next_edge in self.node[now_edge]:
                #インデックスを利用したいときは要修正
                if cal_node_num_arr[next_edge]<=0:
                    continue
                cal_node_num_arr[now_edge]-=1
                cal_node_num_arr[next_edge]-=1
                q[last_ind]=next_edge
                self.parent[next_edge]=now_edge
                ##ここにやりたい処理をぶち込む！！
                #######cal_hogehoge()

                #頂点sから各頂点までの距離を計算する
                cal_distance(now_edge,next_edge,distance)
                if distance[next_edge]>1:
                    append_shinseki(now_edge,next_edge)
                last_ind+=1
            now_ind+=1
        return distance





n=int(input())
n_i=[list(map(int,input().split())) for _ in range(n-1)]
#n=2**3
#n_i=[]
for i in range(n,1,-1):
    n_i.append([i,i//2])

g=Graph(n,n-1,n_i,start_zero=False,weight=False)
d_arr=g.bfs()
three=[]
l=len(g.three)
for i in range(l):
    if len(g.three[i])==0:
        continue
    each=g.three[i]
    for j in each:
        three.append([j,i])
        g.three[j].add(i)
ans=[-1 for _ in range(n)]
now=1
for i in range(n):
    if ans[i]!=-1:
        continue
    ans[i]=now
    now+=1
    for j in g.three[i]:
        if ans[j]!=0:
            ans[j]=now
            now+=1
a=" ".join(map(str,ans))
print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [3]*n
for i in a:
  print(a, end=' ')

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10**6)

def dfs(i, depth):
    visited[i] = True
    oe = depth%2
    ans[i-1] = oe
    count[oe] += 1
    nodes = tree[i]
    for node in nodes:
        if visited[node]:
            continue
        dfs(node, depth+1)
    


N = int(input())
ans = [-1]*N
tree = [[] for i in range(N+1)]
visited = [False]*(N+1)
count = [0, 0]
base = [1, 2, 3]
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a] += [b]
    tree[b] += [a]
dfs(1, 0+1)
if count[0] >= count[1]:
    for i, oe in enumerate(ans):
        if base[oe] > N:
            ans[i] = str(base[2])
            base[2] += 3
        else:
            ans[i] = str(base[oe])
            base[oe] += 3
else:
    for i, oe in enumerate(ans):
        oe = (oe+1)%2
        if base[oe] > N:
            ans[i] = str(base[2])
            base[2] += 3
        else:
            ans[i] = str(base[oe])
            base[oe] += 3
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n-1)]

V = [0] * (n+1)
PP = [[] for i in range(n+1)]

M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

# 1始まりの場合
Q = [[0,0,0] for i in range(n+10)]
Q[0] = [1,-1,-1]
s = 0
r = 1
V[1] = 1
while s < r:
    # print(Q)
    i = Q[s][0]
    p = Q[s][1]
    pp = Q[s][2]
    if pp >= 0:
        for y in M[pp]:
            if y != p:
                PP[y].append(i)
                PP[i].append(y)

    for x in M[i]:
        if V[x] == 0:
            V[x] = 1
            # Q.append([x, i, p])
            Q[r] = [x,i,p]
            r += 1
    s += 1
# print(PP)
vv = -1
V = [0] * (n+1)
for i in range(len(PP)):
    if len(PP[i]) == 0:
        vv += 1
        V[i] = -1
# print(vv)
mi = vv

J = [n//3 for i in range(3)]
if n%3==1:
    J[1] += 1
elif n%3==2:
    J[1] += 1
    J[2] += 1
# print(J)
# J[1] = max(0, J[1] - vv//2)
# J[2] = max(0, J[2] - vv//2)
# if vv%2==1:
#     J[1] = max(0, J[1] - 1)
# print(J)

# print("V",V)
# r = -1
# R = [[], []]
QQ = [[] for i in range(n+1)]
c0 = -1
for ii in range(n+1):
    if V[ii] == 0:
        c0 += 2
        # r += 1
        Q = [[ii,c0]]
        # print(Q)
        
        s = 0
        V[ii] = c0
        while s < len(Q):
            # print(Q)
            i = Q[s][0]
            cc = Q[s][1]
            # if p >= 0:
            #     for y in PP[p]:
            #         if y != i:
            #             QQ[y].append(i)
            #             R[r].append(y)
            #             # QQ[i].append(y)

            for x in PP[i]:
                if V[x] == 0:
                    V[x] = cc+1 if cc%2==1 else cc-1
                    Q.append([x,V[x]])
            s += 1
# print("V",V)

# print(QQ)
R = [[] for i in range(6)]
for i in range(n+1):
    if V[i] >= 1:
        R[V[i]-1].append(i)

# if len(R[1]) > len(R[0]):
#     R = [R[1], R[0]]


# print("R",R)
JJ = [[0,1,0,1,0,1],[0,1,0,1,1,0],
[0,1,1,0,0,1],[0,1,1,0,1,0],[1,0,0,1,0,1],
[1,0,0,1,1,0],[1,0,1,0,0,1],[1,0,1,0,1,0]]

ok = 0
for jj in range(8):
    if ok == 1:
        break
    le = [0,0]
    for kk in range(6):
        # print(JJ[jj][kk])
        # print(R)
        # print(R[kk])
        le[JJ[jj][kk]] += len(R[kk])
        
    if max(0, J[1]-le[0]) + max(0, J[2]-le[1]) <= mi:
        RR = [[],[]]
        for kk in range(6):
            RR[JJ[jj][kk]] += R[kk]
        R = RR
        # print("R",R)
        ANS = [-1] * n
        ok = 1
        for i in R[0]:
            if J[1]==0:
                break
            ANS[i-1] = 1
            J[1] -= 1

        for i in R[1]:
            if J[2] == 0:
                break
            ANS[i-1] = 2
            J[2] -= 1
            
        tt = 0
        # print(ANS)
        for i in range(len(ANS)):
            if ANS[i] == -1:
                while J[tt] == 0:
                    tt += 1
                ANS[i] = tt
                J[tt] -= 1
        # print(J)
        # print(ANS)

        K = [1,0,0]
        for i in range(len(ANS)):
            ANS[i] += K[ANS[i]%3] * 3
            K[ANS[i]%3] += 1
        # print(ANS)
        print(" ".join([str(i) for i in ANS]))

if ok == 0:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

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

grand_sum = [0 for _ in range(n)]
for i in range(n):
	grand_sum[i] = sum([len(adj[x]) for x in adj[i]]) - len(adj[i])

if n <= 3:
	print(*list(range(1, n+1)))
	sys.exit()

ans = [-1 for _ in range(n)]
#ONE, TWO = n//3 + (n%3 > 0), n//3 + (n%3 > 1)

tri = [0 for _ in range(n)]
for a, b in edges:
	tri[b] += grand_sum[a] - len(adj[b]) + 1
	tri[a] += grand_sum[b] - len(adj[a]) + 1
	#print(a, b)
	#print(tri_a, tri_b)
	#print("---")
#print(tri)

#THREE = 3
#for i, t in enumerate(tri):
#	if t >= n - (n//3):
#		if THREE > n:
#			print(-1)
#			sys.exit()
#		ans[i] = THREE
#		THREE += 3

flg = False
orig = -1
for i, t in enumerate(tri):
	if t > n - (n//3):
		flg = True
		orig = i

#parity = [0, 0]
signs = [-1 for _ in range(n)]
def dfs(x):
	for v in adj[x]:
		if signs[v] < 0:
			signs[v] = 1 ^ signs[x]
			dfs(v)

signs[0] = 0
dfs(0)

if flg:
	cur = [1, 2, 3]
	for i in range(n):
		if signs[i] == signs[orig]:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] <= n:
			ans[i] = cur[0]
			cur[0] += 3
		elif cur[1] <= n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[2]
			cur[2] += 3
	print(*ans)
	sys.exit()

num1 = sum(signs)
num2 = n - num1

#print(signs)

M, m = max(num1, num2), min(num1, num2) 
#if max(num1, num2) > n - (n // 3):
#	print(-1)
#	sys.exit()
#else:
if num1 > num2:
	one, two = num1, num2
	more = 1
else:
	one, two = num2, num1
	more = 0
cur = [2, 1, 3]
for i in range(n):
	if ans[i] > 0:
		continue
	if signs[i] == more:
		if cur[1] > n and cur[2] <= n: 
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[1] > n and cur[2] > n:
			ans[i] = cur[0]
			cur[0] += 3
		else:
			ans[i] = cur[1]
			cur[1] += 3
	else:
		if cur[0] > n and cur[2] <= n:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] > n and cur[2] > n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[0]
			cur[0] += 3
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = lr()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    pair = [[] for _ in range(N)]
    for i in range(N):
        dist = [-1]*N
        s = [i]
        dist[i] = 0
        while len(s) > 0:
            v = s.pop()
            for j in edges[v]:
                if dist[j] == -1:
                    dist[j] = dist[v]+1
                    if dist[j] == 3:
                        if i < j:
                            pair[i].append(j)
                            pair[j].append(i)
                        continue
                    s.append(j)
    one = N//3+min(1, N%3)
    two = N//3+N%3//2
    thr = N//3
    ans = [1]*N
    for i in range(N):
        if ans[i] == 1:
            for j in pair[i]:
                if two > 0:
                    ans[j] = 3*two-1
                    two -= 1
                elif thr > 0:
                    ans[j] = 3*thr
                    thr -= 1
                else:
                    print('-1')
                    return
        elif ans[i] == 2:
            for j in pair[i]:
                if ans[j] == 2:
                    if thr > 0:
                        ans[j] = 3*thr
                        thr -= 1
                    else:
                        print('-1')
                        return
    for i in range(N):
        if one == 0 and two == 0:
            break
        elif ans[i] == 1:
            if two > 0:
                ans[i] = 3*two-1
                two -= 1
            elif thr > 0:
                ans[i] = 3*thr
                thr -= 1
            else:
                ans[i] = 3*one-2
                one -= 1
    print(*ans, sep=' ') 
resolve()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import queue

def main():
    N=I()
    adj=[[] for _ in range(N)]
    mod1=range(1,N+1,3)
    n1=0
    mod2=range(2,N+1,3)
    n2=0
    mod3=range(3,N+1,3)
    n3=0
    
    p=[0]*N
    
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
     
    
    q=queue.Queue()
    q.put((0,-1,0))#node,par,depth
    d=[0]*N#深さをメモ
            
        
    while not q.empty():
        v,par,depth=q.get()
        d[v]=depth%2
                
        for i in range(len(adj[v])):
            nxt=adj[v][i]
            if nxt!=par:
                q.put((nxt,v,depth+1))
                
    dmod=[0,0]
    for i in range(N):
        dmod[d[i]]+=1
        
    for i in range(N):
        bit=d[i]
        if dmod[bit]<dmod[(bit+1)%2]:
            if n3<len(mod3):
                p[i]=mod3[n3]
                n3+=1
            elif bit==1:
                if n1<len(mod1):
                    p[i]=mod1[n1]
                    n1+=1
                else:
                    p[i]=mod2[n2]
                    n2+=1
            else:
                if n2<len(mod2):
                    p[i]=mod2[n2]
                    n2+=1
                else:
                    p[i]=mod1[n1]
                    n1+=1
                
        else:
            if bit==1:
                if n1<len(mod1):
                    p[i]=mod1[n1]
                    n1+=1
                elif n3<len(mod3):
                    p[i]=mod3[n3]
                    n3+=1
                else:
                    p[i]=mod2[n2]
                    n2+=1
            else:
                if n2<len(mod2):
                    p[i]=mod2[n2]
                    n2+=1
                elif n3<len(mod3):
                    p[i]=mod3[n3]
                    n3+=1
                else:
                    p[i]=mod1[n1]
                    n1+=1
            
        
                    
                
    
                
    print(' '.join(map(str, p)))
        
        
    
    
        
                
            
        
        
    

main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
L = [-1]*n
dist = [-1]*n
dist[0] = 0
F_1 = [i for i in range(1, n+1) if i%3==1]
F_2 = [i for i in range(1, n+1) if i%3==2]
F_0 = [i for i in range(1, n+1) if i%3==0]
def dfs(v):
  for nv in T[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v] + 1
      dfs(nv)
dfs(0)
K = sorted([(j, i) for i, j in enumerate(dist)], reverse=True)
for d, num in K:
  if F_0:
    L[num] = F_0.pop()
  elif F_2:
    L[num] = F_2.pop()
  else:
    L[num] = F_1.pop()
print(*L)