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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
node_dict = {}
ans_dict = {}
ans_count = {}
def check(i, old_no, deep, start):
    deep += 1
    if deep == 3:
        if i in ans_dict:
            ans_dict[i].append(start)
            ans_count[i] += 1
        else:
            ans_dict[i] = [start]
            ans_count[i] = 1
        if start in ans_dict:
            ans_dict[start].append(i)
            ans_count[start] += 1
        else:
            ans_dict[start] = [i]
            ans_count[start] = 1
        return 0
    for key in node_dict[i]:
        if key == old_no:
            continue
        check(key, i, deep, start)
    return 0

n = int(input())
ans_list = [0] * n
for i in range(1, n):
    a, b  = map(int, input().split())
    if a in node_dict:
        node_dict[a].append(b)
    else:
        node_dict[a] = [b]
    if b in node_dict:
        node_dict[b].append(a)
    else:
        node_dict[b] = [a]

for i in range(1, n):
    for key in node_dict[i]:
        check(key, i, 0, i)

count = 0
count_12 = 0
count_3 = 0
for key, v in sorted(ans_count.items(), key=lambda x: -x[1]):
    if count == n:
        break
    if ans_list[key - 1] == 0:
        if (count_3 + 1) * 3 <= n:
            count += 1
            count_3 += 1
            ans_list[key - 1] = 3 * count_3
            for key1 in ans_dict[key]:
                if ans_list[key1 -1] == 0:
                    count_12 += 1
                    if count_12 % 3 == 0:
                        count_12 += 1
                    ans_list[key1 -1] = count_12
        else:
            count_12 += 1
            if count_12 % 3 == 0:
                count_12 += 1
            ans_list[key - 1] = count_12

for i in range(0, n):
    if ans_list[i] == 0:
        count_12 += 1
        if count_12 % 3 == 0:
            count_12 += 1
        ans_list[i] = count_12
    print(str(ans_list[i]), end="")
    print(" ", end="")

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
connection = [[] for _ in range(N+1)]
distance3 = [[] for _ in range(N+1)]
remain = [i for i in range(1,N+1)]
Nesessary = [False for _ in range(N+1)]



for node in ab:
    connection[node[0]].append(node[1])
    connection[node[1]].append(node[0])

conne_num = [[i+1, 0] for i in range(N)]

p = 0
for conne in connection[1:]:
    p += 1
    for current1 in conne:
        for current2 in connection[current1]:
            for current3 in connection[current2]:
                if current3 not in conne:
                    distance3[p].append(current3)
                    conne_num[p-1][1] += 1
                    Nesessary[p] = True

conne_num = sorted(conne_num, key=lambda x:int(x[1]), reverse =True)

answer = [0] * (N+1)

for p, conn in enumerate(distance3):
    if len(conn) > 0:
        for i in remain:
           if i % 3 == 0:
               answer[p] = i
               remain.remove(i)
               for q in conn:
                   distance3[q].remove(p)
               break
        else:
            print(-1)
            sys.exit()

for i in range(1,N+1):
    if answer[i] == 0:
        answer[i] = remain[0]
        del remain[0]


print(" ".join(map(str,answer[1:])))

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

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

c = 0
for i in range(N):
    f = [0]*N
    f[i] = 1
    s = []
    t = []
    for j in A[i]:
        if f[j] == 0:
            f[j] = 1
            s.append(j)
    for j in s:
        for k in A[j]:
            if f[k] == 0:
                f[k] = 1
                t.append(k)
        for k in t:
            for l in A[k]:
                if f[l] == 0:
                    f[l] = 1
                    P[i].append(l)
                    c += 1

g = [[i] for i in range(N)]
for i in range(N):
    g[i].append(len(P[i]))
g = sorted(g, key=lambda x:x[1], reverse=True)

ans = [0]*N
check = [-1]*N
for i in range(N//3):
    ans[g[i][0]] = 3*(i+1)
    check[g[i][0]] = 0

iti = 0
ni = 0

k = 0
for i in range(N):
    if ans[i] == 0:
        if len(P[i]) == 0:
            if iti <= ni:
                ans[i] = 3 * iti + 2
                iti += 1
                check[i] = 1
            else:
                ans[i] = 3 * ni + 1
                ni += 1
                check[i] = 2

        for j in P[i]:
            if check[j] == 1:
                if ans[i] % 3 == 1:
                    k = 1
                else:
                    if ans[i] == 0:
                        if ni > N//3:
                            k = 1
                        else:
                            ans[i] = 3*ni + 2
                            ni += 1
                            check[i] = 2
            elif check[j] == 2:
                if ans[i] % 3 == 2:
                    k = 1
                else:
                    if ans[i] == 0:
                        if iti > N//3:
                            k = 1
                        else:
                            ans[i] = 3*iti + 1
                            iti += 1
                            check[i] = 1

            else:
                if iti <= ni:
                    ans[i] = 3 * iti + 2
                    iti += 1
                    check[i] = 1
                else:
                    ans[i] = 3 * ni + 1
                    ni += 1
                    check[i] = 2

if k == 1:
    print(-1)
else:
    print(ans)

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
        else:
            if (ans[j]+ans[i])%3!=0 and (ans[j]*ans[i])%3!=0:
                print(-1)
                exit()
a=" ".join(map(str,ans))
print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
tree = [[] for i in range(N)]

ans = [i for i in range(1,N+1)]

for i in range(N-1):
    pair = [int(i) for i in input().split()]
    tree[pair[0]-1].append(pair[1]-1)
    tree[pair[1]-1].append(pair[0]-1)

b = []
for i in range(N):
    a = []
    for idx_1 in tree[i]:
        tmp = [j for j in tree[idx_1] if j != i and j != idx_1]
        if len(tmp) > 0:
            for idx_2 in tmp:
                a = a + [j for j in tree[idx_2] if j != i and j != idx_1 and j != idx_2]

    if len(a)>0:
        for p in a:
            if p > i:
                ans[p] = ans[i] * 3

print(" ".join([str(i) for i in ans]))

Submission status: Wrong Answer

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

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

class TREE(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()
        # self.doubling()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]


depth = TREE(es).depth


# def dist(u,v):
#     return lca.depth[a - 1] + lca.depth[b - 1] - 2 * lca.depth[lca.get(a - 1, b - 1)]
ans = [0]*n

ans = [1 if d % 2 == 0 else 2 for d in depth]

zero = one = two = n // 3
if n % 3 == 1: one += 1
if n % 3 == 2:
    one+=1
    two+=1


flg = 1

for i in range(n):
    if depth[i] % 2 == 0:
        if one >= 0:
            ans[i] = one*3 + 1
            one -= 1
        elif zero >= 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg = -1
            break
    else:
        if two >= 0:
            ans[i] = two*3 + 2
            two -= 1
        elif zero >= 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg = -1
            break

if flg == 1:
    print(*ans, sep='')
    exit()

flg2 = 1


zero = one = two = n // 3


for i in range(n):
    if depth[i] % 2 == 1:
        if one >= 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero >= 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg2 = -1
            break
    else:
        if two >= 0:
            ans[i] = two*3 + 2
            two -= 1
        elif zero >= 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg2 = -1
            break

if flg == 1:
    print(*ans, sep='')
    exit()

print(-1)

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]
               
                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 Son[Par[nowNode]]:
                if son != 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
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]]
        Q = [[0,0] for i in range(n+2)]
        Q[0] = [ii,c0]
        r = 1
        # 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]])
                    Q[r] = [x,V[x]]
                    r += 1
            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 = [3,0,0]
        for i in range(len(ANS)):
            ip = ANS[i]%3
            ANS[i] += K[ip]
            K[ip] += 3
        # print(ANS)
        print(" ".join([str(i) for i in ANS]))

if ok == 0:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
node_dict = {}
ans_dict = {}
ans_count = {}
def check(i, old_no, deep, start):
    deep += 1
    if deep == 3:
        if i in ans_dict:
            ans_dict[i].append(start)
            ans_count[i] += 1
        else:
            ans_dict[i] = [start]
            ans_count[i] = 1
        if start in ans_dict:
            ans_dict[start].append(i)
            ans_count[start] += 1
        else:
            ans_dict[start] = [i]
            ans_count[start] = 1
        return 0
    for key in node_dict[i]:
        if key == old_no:
            continue
        check(key, i, deep, start)
    return 0

n = int(input())
ans_list = [0] * n
for i in range(1, n):
    a, b  = map(int, input().split())
    if a in node_dict:
        node_dict[a].append(b)
    else:
        node_dict[a] = [b]
    if b in node_dict:
        node_dict[b].append(a)
    else:
        node_dict[b] = [a]

for i in range(1, n):
    for key in node_dict[i]:
        check(key, i, 0, i)

count = 0
count_12 = 0
count_3 = 0
for key, v in sorted(ans_count.items(), key=lambda x: -x[1]):
    if count == n:
        break
    if ans_list[key - 1] == 0:
        if (count_3 + 1) * 3 <= n:
            count += 1
            count_3 += 1
            ans_list[key - 1] = 3 * count_3
            for key1 in ans_dict[key]:
                if ans_list[key1 -1] == 0:
                    count_12 += 1
                    if count_12 % 3 == 0:
                        count_12 += 1
                    ans_list[key1 -1] = count_12
        else:
            count_12 += 1
            if count_12 % 3 == 0:
                count_12 += 1
            ans_list[key - 1] = count_12

for i in range(0, n):
    if ans_list[i] == 0:
        count_12 += 1
        if count_12 % 3 == 0:
            count_12 += 1
        ans_list[key - 1] = count_12
    print(str(ans_list[i]), end="")
    print(" ", end="")

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat)


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def lowestCommonAncestor(graph, root, p, q):
    pass
        # node_parent = {}  # key: node, value: node's parent
        # queue = deque([root])
        # # traverse all nodes by BST and construct node_parent map
        # while queue:
        #     edge = queue.popleft()
        #     nxt = graph[edge]
        #     if node.left:
        #         node_parent[node.left] = node
        #         queue.append(node.left)
        #     if node.right:
        #         node_parent[node.right] = node
        #         queue.append(node.right)

        # constcurt node existence on paths of p
        # In python, we can use set instead of dictionary
        # because it also takes O(1) to check value existence
        # pParents = set()
        # current = p
        # while current in node_parent:
        #     pParents.add(current)
        #     current = node_parent[current]
        # else:
        #     pParents.add(current)

        # # find first common node on paths of p and q
        # current = q
        # while current not in pParents:
        #     current = node_parent[current]
        # return current


def bfs(graph, initial, N):
    n = len(graph) - 1
    dist = [-1] * (n + 1)
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True
    dist[initial] = 0
    levels = [[] for i in range(N)]
    levels[0].append(initial)
    node_parent = {}

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]

        for i, e in enumerate(nxt):
            if visited[e] is False:
                q.append(e)
                dist[e] = dist[edge] + 1
                levels[dist[e]].append(e)
                node_parent[e] = edge
                visited[e] = True

    return levels, node_parent


def main():
    N = I()
    # n = Segtree(10**5, )
    graph = [[] for i in range(N+1)]
    children = [[] for i in range(N+1)]
    # parents = [[] for i in range(N+1)]

    for i in range(N-1):
        x, y = MI()
        graph[x].append(y)
        graph[y].append(x)

    children = [set(i) for i in graph]

    levels, node_parent = bfs(graph, 1, N)
    # print(levels)
    # print(node_parent)
    # print(children)
    pairs = [[] for i in range(N+1)]

    for i in range(N-1):
        if i < N - 3:
            nodes = levels[i+3]
            for j in range(len(nodes)):
                pairs[i+1].append(nodes[j])

    for i in range(2, N):
        parent = node_parent[i]
        d_2 = children[parent]
        # print(i, parent)
        for node in d_2:
            if parent in node_parent and node == node_parent[parent]:
                continue

            if node == parent or node == i:
                continue

            for d_3 in children[node]:
                if d_3 != parent and d_3 != i:
                    # pairs.append((i, d_3))
                    pairs[i].append(d_3)
                # print(node, children[node])

        # if i > 0:
        #     parents = levels[i]
        #     for parent in parents:
                # nodes = levels[i+1]
                # for j in range(len(nodes)):
                #     if nodes[j] not in children[parent]:
                #         pairs.append((parent, nodes[j]))

    # print(pairs)
    m = [False] * (N+1)
    p = [0] * N
    cur = 1
    for p1 in range(1, N):
        if m[p1-1] is False:
            p[p1-1] = cur
            m[p1-1] = True
        for i in range(len(pairs[p1])):
            # print(target, p2)
            p2 = pairs[p1][i]
            if m[p2-1] is False:
                target = p[p1-1] + 3 * (i+1)
                p[p2-1] = target
                m[p2-1] = True
            else:
                if p[p1-1] + p[p2-1] % 3 == 0 or p[p1-1] * p[p2-1] % 3 == 0:
                    continue
                else:
                    print(-1)
                    return
        cur += 1

    print(*p)
    # for p1, p2 in pairs:
        # if m[cur] is False:
        #     m[cur] = True
        #     p[p1-1] = cur
        #     cur + 3



if __name__ == '__main__':
    main()

# 11
# 1 2
# 1 3
# 1 4
# 2 5
# 2 6
# 3 7
# 3 8
# 4 9
# 5 11
# 9 10

Submission status: Wrong Answer

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

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

from collections import deque, Counter

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

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

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

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

ans = [0]*n
if x<y:
    one, two = two, one
aaaa = [(-len(G[i]), i) for i in range(n)]
aaaa.sort()
for _, i in aaaa:
    if i in ok:
        continue
    if dep1[i]%2 == 0:
        if three:
            ans[i] = three.pop()
        elif one:
            ans[i] = one.pop()
        else:
            ans[i] = two.pop()
    else:
        if three:
            ans[i] = three.pop()
        elif two:
            ans[i] = two.pop()
        else:
            one.pop()

res = one+two+three
for i in ok:
    ans[i] = res.pop()

print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
from collections import defaultdict
flag = [0 for i in range(N)]
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

numbers1 = [i for i in range(1, N+1) if i % 3 == 1]
numbers2 = [i for i in range(1, N+1) if i % 3 == 2]
numbers3 = [i for i in range(1, N+1) if i % 3 == 0]

dic = defaultdict(int)
for idx, d in enumerate(dist):
    dic[d] += 1

al = []
for idx, d in enumerate(dist):
    al.append((dic[d], d, idx))

ansl = [-1 for i in range(N)]
al = sorted(al, reverse=True)
for amount, d, idx in al:
    if d % 2 == 0:
        if numbers1:
            ansl[idx] = numbers1.pop()
        elif numbers3:
            ansl[idx] = numbers3.pop()
        else:
            ansl[idx] = numbers2.pop()
    else:
        if numbers2:
            ansl[idx] = numbers2.pop()
        elif numbers3:
            ansl[idx] = numbers3.pop()
        else:
            ansl[idx] = numbers1.pop()
for a in ansl:
    print(a)