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

def BFS(graph, start, end):
    search_dict = {}
    mark_dict = {}
    queue = deque([start])
    mark_dict[start] = 0
    while len(queue) > 0:
        target = queue.pop()
        if mark_dict[target] > 3:
            break
        if target not in search_dict:
            if target != end:
                for elem in graph[target]:
                    search_dict[target] = True
                    mark_dict[elem] = mark_dict[target] + 1
                    queue.appendleft(elem)
            else:
                return mark_dict[target] == 3
    return False

n = int(input())
graph = {}
for i in range(n-1):
    a, b = map(str, input().split())
    if not(a in graph):
        graph[a] = []
    if not(b in graph):
        graph[b] = []
    graph[a].append(b)
    graph[b].append(a)

result = []
calc = [[False] * (n + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(n - i):
        newi = i + 1
        newj = j + 1
        if (newi + newj) % 3 == 0 or newi * newj % 3 == 0:
            calc[newj][newi] = True
            calc[newi][newj] = True
        if newi == newj + i:
            continue
        if BFS(graph, str(newi), str(newj + i)):
            result.append([newi, newj + i])


for per in list(permutations(range(n))):
    ok = True
    for test in result:
        if calc[per[int(test[0]) - 1]][per[int(test[1]) - 1]]:
            continue
        ok = False
    if ok:
        print(per)

print("-1")

Submission status: Wrong Answer

Solution code:
import math
from sys import stdin
from collections import defaultdict
from collections import deque
import heapq

N = int( input())
Cs = [list(map(int,stdin.readline().split()))for _ in range(N -1 )]
INF = 10 ** 15
assign = [-1] * (N + 1)
tree_child_num= [0] * (N + 1) #子供の人数
tree_gen= [0] * (N + 1) #自分の世代
tree_mago = [0] * (N + 1)
tree_himago = [0] * (N + 1) # ひ孫の人数
tree_childs = [[]for _ in  range (N + 1)] # 自分の子供の番号のリスト
tree_nan =  [0] * (N + 1) #自分が何人目の子供か
tree_parens = [0] * (N + 1) #自分の親
tree_sansyou = [0] * (N + 1)
visit = [False] * (N + 1)
graph_connection = defaultdict(lambda :[])
#,何人目の子供か
# (自分の世代+何人目の子供)  で1余る数か2余る数かの割当を決める
# #親の孫の人数 - 自分の子供の人数 + 自分のひ孫の人数
for C in  Cs:
    a,b = C
    graph_connection[a].append(b)
    graph_connection[b].append(a)

que = deque()

que.append(1)
gen = 0
child_num = 0
tree_gen[1] = 0
visit[1] = True
while que:
    v_num = que.pop()
    connects = graph_connection[v_num]
    child_num = 0
    for i in connects:
        if not visit[i]:
            que.append(i)
            tree_gen[i] = tree_gen[v_num] + 1
            tree_nan[i] = child_num
            child_num += 1
            tree_childs[v_num].append(i)
            visit[i] = True
            tree_parens[i] = v_num
            if tree_gen[i] > 1: #孫なら、祖父にフィードバック
                sohu = tree_parens[v_num]
                tree_mago[sohu] += 1
            if tree_gen[i] > 2: #ひ孫なら、曽祖父にフィードバック
                sosohu = tree_parens[sohu]
                tree_himago[sosohu] += 1
    tree_child_num[v_num] = child_num
# for i in range(1,N + 1):
heq  = []
for i in range(1,N+ 1):
    par = tree_parens[i]
    tree_sansyou[i] = tree_himago[i] + tree_mago[par] - tree_child_num[i]
    if tree_sansyou[i]  > 0 or tree_mago[par] - tree_child_num[i]:
        heapq.heappush(heq,(-tree_sansyou[i] , i)) #優先度、番号

#割当フェイズ
ind_0 = 0
lim_0 = N//3
ind_1 = 0
lim_1 = math.ceil ((N - 1)//3) + 1
ind_2 = 0
lim_2 = math.ceil ((N - 2)//3) + 1
while heq: #制約付きの割当
    _,num = heapq.heappop(heq)
    if ind_0 < lim_0:
        assign[num] = (ind_0 + 1) * 3
        ind_0 += 1
    else:
        if tree_nan[num] + tree_gen[num] % 2 == 0: #2を割り当てる
            if ind_1 == lim_1: #割当が足りなくなったら
                print(-1)
                exit(0)
            else:
                assign[num] = (ind_1 ) * 3 + 1
                ind_1 += 1
        else:
            if ind_2 == lim_2: #割当が足りなくなったら
                print(-1)
                exit(0)
            else:
                assign[num] = (ind_2) * 3 + 2
                ind_2 += 1

#残りの数字を割り当てる
for num in range(1,N + 1):
     if assign[num] == -1:
        if ind_0 < lim_0:
            assign[num] = (ind_0 + 1) * 3
            ind_0 += 1

        elif ind_1 < lim_1:
            assign[num] = (ind_1) * 3 + 1
            ind_1 += 1

        elif ind_2 < lim_2:
            assign[num] = (ind_2) * 3 + 2
            ind_2 += 1


print(*assign[1:])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N = n_in()
edges = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = l_in()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


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

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


root = 0

for i in range(N):
    root = max(len(edges[root]), len(edges[i]))
dfs(root, 0)


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

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

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


print_l(res)

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    deg[a] += 1
    deg[b] += 1


q = deque([deg.index(1)])
num = [-1] * n
num[q[0]] == 1
nnn = [0] * 3
d = 2
while q:
    x = q.popleft()
    for y in G[x]:
        if num == -1:
            q.append(y)
            num[y] = d
            nnn[d%3] += 1
        d += 1
ans = [0] * n
aa = nnn.index(max(nnn)) % 3
nnn = [1, 2, 3]
for i in range(n):
    x = (num[i]- aa) % 3
    ans[i] = nnn[x]
    nnn[x] += 3
print(*ans)







print(*ans)

Submission status: Wrong Answer

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


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

Cl = [-1]*N
C = [[0], []]
q = [0]
c = 0
Cl[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np in graph[p]:
            if Cl[np]  == -1:
                Cl[np] = c
                C[c].append(np)
                qq.append(np)
    q = qq

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

c0 = (N+2)//3
c1 = (N+1)//3
c2 = N//3
Co = [[], [], []]
if len(C[0]) < c1:
    R = set(C[0])
    for p in range(N):
        if p in R:
            Co[2].append(p)
        elif len(Co[0]) < c0:
            Co[0].append(p)
        elif len(Co[1]) < c1:
            Co[1].append(p)
        else:
            Co[2].append(p)
else:
    R2 = set(C[0])
    for p in range(N):
        if p in R2: # larger
            if len(Co[0]) < c0:
                Co[0].append(p)
            else:
                Co[2].append(p)
        else: # smaller
            if len(Co[1]) < c1:
                Co[1].append(p)
            else:
                Co[2].append(p)

ans = [None]*N
for i, n in enumerate(Co[0]):
    ans[n] = 3*i+1
for i, n in enumerate(Co[1]):
    ans[n] = 3*i+2
for i, n in enumerate(Co[2]):
    ans[n] = 3*i+3


print(*ans)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def eulerian_trail(tree, max_v, root=0):
    """
    木のオイラー路; オイラーツアー
    :param list of (list of (int, int)) tree:
    :param int max_v:
    :param int root:
    :return: (trails, depths, weights)
    :rtype: (list of int, list of int, list of int)
    """
    seen = [False] * (max_v + 1)
    # 頂点の履歴
    trails = []
    # 深さの履歴
    depths = []
    # 距離の履歴
    weights = []
    # Overflow 回避のためループで
    stack = [(root, 0, 0, True)]
    while stack:
        v, d, w, forward = stack.pop()
        seen[v] = True
        trails.append(v)
        depths.append(d)
        weights.append(w)
        if not forward:
            continue

        for u, w in tree[v]:
            if not seen[u]:
                stack.append((v, d, -w, False))
                stack.append((u, d + 1, w, True))
    return trails, depths, weights


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]

# AB = generate_tree(N)
# plot_graph(AB)
# for a, b in AB:
#     graph[a].append((b, 1))
#     graph[b].append((a, 1))

for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append((b, 1))
    graph[b].append((a, 1))

counts = [N // 3, (N + 2) // 3, (N + 1) // 3]

# 二部グラフ
vs, _, _ = eulerian_trail(graph, N - 1)
bp = [0] * N
for i, v in enumerate(vs):
    bp[v] = i & 1


ansmod = [-1] * N
if bp.count(0) <= counts[0]:
    # 3を割り当てる
    for v, b in enumerate(bp):
        if b == 0 and counts[0] > 0:
            ansmod[v] = 0
            counts[0] -= 1
elif bp.count(1) <= counts[0]:
    # 3を割り当てる
    for v, b in enumerate(bp):
        if b == 0 and counts[0] > 0:
            ansmod[v] = 0
            counts[0] -= 1
else:
    # 違う方に違うのを割り当てる
    for v, b in enumerate(bp):
        if b == 0 and counts[1] > 0:
            ansmod[v] = 1
            counts[1] -= 1
        if b == 1 and counts[2] > 0:
            ansmod[v] = 2
            counts[2] -= 1
    assert counts[1] == counts[2] == 0
# 残りに余ってるのを割り当てる
for v in range(N):
    if ansmod[v] < 0:
        for i in range(3):
            if counts[i] > 0:
                ansmod[v] = i
                counts[i] -= 1
                break

ans = []
M = [3, 1, 2]
for a in ansmod:
    ans.append(M[a])
    M[a] += 3
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
Ki = defaultdict(list)

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

parity = [-1]*N
nekko = 0
parity[0] = 1
que = [[0,1]]
visited = [-1]*N

while que !=[]:
    now,pari = que.pop()
    parity[now] = pari
    visited[now] = 1
    for i in Ki[now]:
        if visited[i] ==-1:
            que.append([i,-1*pari])
#print(parity)

zero = 1
one = 0
two = 0
M = N//3
    
Ans = []
for i in parity:
    if i==1:
        if one<=M:
            Ans.append(3*one+1)
            one+=1
        else:
            Ans.append(3*zero)
            zero+=1
    elif i==-1:
        if two<=M:
            Ans.append(3*two+2)
            two+=1
        else:
            Ans.append(3*zero)
            zero+=1
print(*Ans)

Submission status: Wrong Answer

Solution code:
import math
from sys import stdin
from collections import defaultdict
from collections import deque
import heapq

N = int( input())
Cs = [list(map(int,stdin.readline().split()))for _ in range(N -1 )]
INF = 10 ** 15
assign = [-1] * (N + 1)
tree_child_num= [0] * (N + 1) #子供の人数
tree_gen= [0] * (N + 1) #自分の世代
tree_mago = [0] * (N + 1)
tree_himago = [0] * (N + 1) # ひ孫の人数
tree_childs = [[]for _ in  range (N + 1)] # 自分の子供の番号のリスト
tree_nan =  [0] * (N + 1) #自分が何人目の子供か
tree_parens = [0] * (N + 1) #自分の親
tree_sansyou = [0] * (N + 1)
visit = [False] * (N + 1)
graph_connection = defaultdict(lambda :[])
#,何人目の子供か
# (自分の世代+何人目の子供)  で1余る数か2余る数かの割当を決める
# #親の孫の人数 - 自分の子供の人数 + 自分のひ孫の人数
for C in  Cs:
    a,b = C
    graph_connection[a].append(b)
    graph_connection[b].append(a)

que = deque()

que.append(1)
gen = 0
child_num = 0
tree_gen[1] = 0
visit[1] = True
while que:
    v_num = que.pop()
    connects = graph_connection[v_num]
    child_num = 0
    for i in connects:
        if not visit[i]:
            que.append(i)
            tree_gen[i] = tree_gen[v_num] + 1
            tree_nan[i] = child_num
            child_num += 1
            tree_childs[v_num].append(i)
            visit[i] = True
            tree_parens[i] = v_num
            if tree_gen[i] > 1: #孫なら、祖父にフィードバック
                sohu = tree_parens[v_num]
                tree_mago[sohu] += 1
            if tree_gen[i] > 2: #ひ孫なら、曽祖父にフィードバック
                sosohu = tree_parens[sohu]
                tree_himago[sosohu] += 1
    tree_child_num[v_num] = child_num
# for i in range(1,N + 1):
heq  = []
for i in range(1,N+ 1):
    par = tree_parens[i]
    tree_sansyou[i] = tree_himago[i] + tree_mago[par] - tree_child_num[i]
    if tree_sansyou[i]  > 0:
        heapq.heappush(heq,(-tree_sansyou[i] , i)) #優先度、番号

#割当フェイズ
ind_0 = 0
lim_0 = N//3
ind_1 = 0
lim_1 = math.ceil ((N - 1)//3) + 1
ind_2 = 0
lim_2 = math.ceil ((N - 2)//3) + 1
while heq: #制約付きの割当
    _,num = heapq.heappop(heq)
    if ind_0 < lim_0:
        assign[num] = (ind_0 + 1) * 3
        ind_0 += 1
    else:
        if tree_nan[num] + tree_gen[num] % 2 == 0: #2を割り当てる
            if ind_1 == lim_1: #割当が足りなくなったら
                print(-1)
                exit(0)
            else:
                assign[num] = (ind_1 ) * 3 + 1
                ind_1 += 1
        else:
            if ind_2 == lim_2: #割当が足りなくなったら
                print(-1)
                exit(0)
            else:
                assign[num] = (ind_2) * 3 + 2
                ind_2 += 1

#残りの数字を割り当てる
for num in range(1,N + 1):
     if assign[num] == -1:
        if ind_0 < lim_0:
            assign[num] = (ind_0 + 1) * 3
            ind_0 += 1

        elif ind_1 < lim_1:
            assign[num] = (ind_1) * 3 + 1
            ind_1 += 1

        elif ind_2 < lim_2:
            assign[num] = (ind_2) * 3 + 2
            ind_2 += 1


print(*assign[1:])

Submission status: Wrong Answer

Solution code:
#  --*-coding:utf-8-*--

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

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


L = [None]*(N+1)
L[0] = 0
L[1] = 0
C = [0]*2

Q = [1]
while len(Q) > 0:
    q = Q.pop()
    nextL = L[q] + 1

    for subNode in E[q]:
        if L[subNode] == None:
            L[subNode] = nextL
            Q.append(subNode)
            C[nextL%2] += 1
            
g1 = 0
g2 = 0
g3 = 1

g1Max = (N+2)//3
g2Max = (N+1)//3

if max(L) < 2:
    print(' '.join([str(i) for i in range(1, N+1)]))

elif C[0] < g2Max or C[1] < g2Max:
    print(-1)

else:
    targetL = 1 if C[0] < C[1] else 0

    X = [None]*(N+1)

    for i in range(1, N+1):
        if L[i]%2 == targetL:
            if g1 < g1Max:
                X[i] = g1*3 + 1
                g1 += 1
            else:
                X[i] = g3*3
                g3 += 1
        else:
            if g2 < g2Max:
                X[i] = g2*3 + 2
                g2 += 1
            else:
                X[i] = g3*3
                g3 += 1

    print(' '.join(map(str, X[1:])))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d = [i % 2+1 for i in d]
    d2 = [0]*n
    j1 = 1
    for i in range(n):
        if d[i] == 1:
            d2[i] = j1
            j1 += 3
            cnt += 1
    j2 = 2
    for i in range(n):
        if d[i] == 2:
            d2[i] = j2
            j2 += 3
    j3 = 3
    for i in range(n):
        if d2[i] > n:
            d2[i] = j3
            j3 += 3
    if j1 > n:
        for i in range(n):
            if d2[i] > n:
                d2[i] = j2
                j2 += 3
    else:
        for i in range(n):
            if d2[i] > n:
                d2[i] = j1
                j1 += 3
    print(*d2)


main()

Submission status: Wrong Answer

Solution code:
import math
from sys import stdin
from collections import defaultdict
from collections import deque
import heapq

N = int( input())
Cs = [list(map(int,stdin.readline().split()))for _ in range(N -1 )]
INF = 10 ** 15
assign = [-1] * (N + 1)
tree_child_num= [0] * (N + 1) #子供の人数
tree_gen= [0] * (N + 1) #自分の世代
tree_mago = [0] * (N + 1)
tree_himago = [0] * (N + 1) # ひ孫の人数
tree_childs = [[]for _ in  range (N + 1)] # 自分の子供の番号のリスト
tree_nan =  [0] * (N + 1) #自分が何人目の子供か
tree_parens = [0] * (N + 1) #自分の親
tree_sansyou = [0] * (N + 1)
visit = [False] * (N + 1)
graph_connection = defaultdict(lambda :[])
#,何人目の子供か
# (自分の世代+何人目の子供)  で1余る数か2余る数かの割当を決める
# #親の孫の人数 - 自分の子供の人数 + 自分のひ孫の人数
for C in  Cs:
    a,b = C
    graph_connection[a].append(b)
    graph_connection[b].append(a)

que = deque()

que.append(1)
gen = 0
child_num = 0
tree_gen[1] = 0
visit[1] = True
while que:
    v_num = que.pop()
    connects = graph_connection[v_num]
    child_num = 0
    for i in connects:
        if not visit[i]:
            que.append(i)
            tree_gen[i] = tree_gen[v_num] + 1
            tree_nan[i] = child_num
            child_num += 1
            tree_childs[v_num].append(i)
            visit[i] = True
            tree_parens[i] = v_num
            if tree_gen[i] > 1: #孫なら、祖父にフィードバック
                sohu = tree_parens[v_num]
                tree_mago[sohu] += 1
            if tree_gen[i] > 2: #ひ孫なら、曽祖父にフィードバック
                sosohu = tree_parens[sohu]
                tree_himago[sosohu] += 1
    tree_child_num[v_num] = child_num
# for i in range(1,N + 1):
heq  = []
for i in range(1,N+ 1):
    par = tree_parens[i]
    tree_sansyou[i] = tree_himago[i] + tree_mago[par] - tree_child_num[i]
    heapq.heappush(heq,(-tree_sansyou[i] , i)) #優先度、番号

#割当フェイズ
ind_0 = 0
lim_0 = N//3
ind_1 = 0
lim_1 = math.ceil ((N - 1)//3) + 1
ind_2 = 0
lim_2 = math.ceil ((N - 2)//3) + 1
while heq: #制約付きの割当
    _,num = heapq.heappop(heq)
    if ind_0 < lim_0:
        assign[num] = (ind_0 + 1) * 3
        ind_0 += 1
    else:
        if tree_nan[num] + tree_gen[num] % 2 == 0: #2を割り当てる
            if ind_1 == lim_1: #割当が足りなくなったら
                print(-1)
                exit(0)
            else:
                assign[num] = (ind_1 ) * 3 + 1
                ind_1 += 1
        else:
            if ind_2 == lim_2: #割当が足りなくなったら
                print(-1)
                exit(0)
            else:
                assign[num] = (ind_2) * 3 + 2
                ind_2 += 1

#残りの数字を割り当てる
for num in range(1,N + 1):
     if assign[num] == -1:
        if ind_0 < lim_0:
            assign[num] = (ind_0 + 1) * 3
            ind_0 += 1

        elif ind_1 < lim_1:
            assign[num] = (ind_1) * 3 + 1
            ind_1 += 1

        elif ind_2 < lim_2:
            assign[num] = (ind_2) * 3 + 2
            ind_2 += 1


print(*assign[1:])

Submission status: Wrong Answer

Solution code:
n = int(input())
a, b = [], []
for i in range(n - 1):
  a1, b1 = list(map(int,input().split()))
  a.append(a1)
  b.append(b1)
  
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]
                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 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


def main():
    input = sys.stdin.readline
    N = int(input())
    G = [set() for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].add(b)
        G[b].add(a)

    # 距離3の点を調べていく
    s = [set() for i in range(N)]
    import collections
    q = collections.deque()
    for i in range(N):
        r = [True]*N
        r[i] = False
        q.append((i, 0))
        while(q):
            x, c = q.popleft()
            if c == 3:
                s[i].add(x)
                continue
            for y in G[x]:
                if r[y]:
                    q.append((y, c+1))
                    r[y] = False

    ans = [-1]*N
    k = [N//3]*3
    for i in range(N % 3):
        k[i] += 1
    r = set()
    #t = set([i+1 for i in range(N)])
    #s.sort(key=lambda x: len(x[1]))
    #q = collections.deque(s)

    for i in range(N):
        s[i] -= r
        for x in s[i]:
            tmp = s[x] & s[i]
            for y in tmp:
                if ans[y] != -1:
                    continue
                if k[2] > 0:
                    ans[y] = k[2] * 3
                    k[2] -= 1
                    r.add()
                    s[i].remove(y)
                else:
                    print(-1)
                    exit(0)
    for i in range(N):
        if ans[i] == -1:
            if k[0] > 0:
                ans[i] = k[0]*3 - 2
                k[0] -= 1
                for x in s[i]:
                    if ans[x] != -1:
                        continue
                    if k[1] > 0:
                        ans[x] = k[1]*3 - 1
                        k[1] -= 1
                    else:
                        ans[x] = k[2]*3
                        k[2] -= 1
            elif k[1] > 0:
                ans[i] = k[0]*3 - 1
                k[1] -= 1
                for x in s[i]:
                    if ans[x] != -1:
                        continue
                    if k[0] > 0:
                        ans[x] = k[0]*3 - 1
                        k[0] -= 1
                    else:
                        ans[x] = k[2]*3
                        k[2] -= 1
            else:
                ans[i] = k[2] * 3
                k[2] -= 1
        else:
            if ans[i] % 3 == 1:
                for x in ans[i]:
                    if ans[x] != -1:
                        continue
                    else:
                        if k[1] > 0:
                            ans[x] = k[1]*3 - 1
                            k[1] -= 1
                        else:
                            ans[x] = k[2]*3
                            k[2] -= 1
            elif ans[i] & 3 == 2:
                for x in s[i]:
                    if ans[x] != -1:
                        continue
                    if k[0] > 0:
                        ans[x] = k[0]*3 - 1
                        k[0] -= 1
                    else:
                        ans[x] = k[2]*3
                        k[2] -= 1

    print(*ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
E = [[] for _ in range(N+1)]

if N == 1:
	print(1)
	sys.exit()
if N == 2:
	print('1 2')
	sys.exit()
 
for i in range(N-1):
  a,b = map(int,input().split())
  E[a].append(b)
  E[b].append(a)

ans = [0] * (N+1)

q = [[1,1]]

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

mod0 = 6
mod1 = 1
mod2 = 2

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

print(*answer)

Submission status: Wrong Answer

Solution code:
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)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

mem = [[[] for _ in range(2)] for _ in range(4)]
for i,d in enumerate(depth):
    if d%2:
        mem[0][0].append(i)
        mem[1][1].append(i)
    else:
        mem[0][1].append(i)
        mem[1][0].append(i)
    if d<=1:
        mem[2][0].append(i)
        mem[3][1].append(i)
    else:
        if ((d-2)//3)%2:
            mem[2][0].append(i)
            mem[3][1].append(i)
        else:
            mem[2][1].append(i)
            mem[3][0].append(i)

for k in range(4):
    ans = [None] * N
    for i in range(1,N+1):
        if i%3==0:
            if len(mem[k][0])==0 and len(mem[k][1])==0:
                break
            if len(mem[k][0]) <= len(mem[k][1]):
                j = mem[k][1].pop()
            else:
                j = mem[k][0].pop()
        elif i%3==1:
            if len(mem[k][0])==0:
                break
            j = mem[k][0].pop()
        else:
            if len(mem[k][1])==0:
                break
            j = mem[k][1].pop()
        ans[j] = i
    else:
        print(*ans)
        exit()
print(-1)