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: Runtime Error

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_himago[i]  > 0 or  tree_mago[par] - tree_child_num[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(1)
            else:
                assign[num] = (ind_1 ) * 3 + 1
                ind_1 += 1
        else:
            if ind_2 == lim_2: #割当が足りなくなったら
                print(-1)
                exit(1)
            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: Runtime Error

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

Submission status: Runtime Error

Solution code:
print(1 2 5 4 3)

Submission status: Runtime Error

Solution code:
# import bisect
from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def pm1():
    print(-1)
    sys.exit()

def main():
    n = int(input())
    nodes = [[] for _ in range(n+1)]

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

    que = deque()
    pair = set()

    for i in range(1,n+1):
        que.append((i,0))
        seen = set()
        while que:
            current_id, dist = que.popleft()
            seen.add(current_id)
            current_node = nodes[current_id]
            if dist == 3:
                if i > current_id:
                    first = current_id
                    second = i
                else:
                    first = i
                    second = current_id
                pair.add((first,second))
            else:
                for nx in current_node:
                    if nx not in seen:
                        que.append((nx,dist+1))

    connect_ele = [[] for _ in range(n+1)]
    connect_cnt = Counter()
    pair_rem = len(pair)

    for p, q in pair:
        connect_ele[p].append(q)
        connect_ele[q].append(p)
        connect_cnt[p] += 1
        connect_cnt[q] += 1

    ans = [0] * n
    num3 = [_ for _ in range(3, n+1, 3)]
    filled = 0

    while num3 and pair_rem>0:
        midx = connect_cnt.most_common()[0][0]
        ans[midx-1] = num3.pop()
        filled += 1
        pair_rem -= connect_cnt.most_common()[0][1]
        connect_cnt[midx] = 0
        for idx in connect_ele[midx]:
            connect_cnt[idx] -= 1

    num1 = [_ for _ in range(1, n+1, 3)]
    ln1 = len(num1)
    num2 = [_ for _ in range(2, n+1, 3)]
    ln2 = len(num2)

    while pair_rem > 0:
        midx = connect_cnt.most_common()[0][0]

        if ln2 > ln1 > 0:
            ans[midx-1] = num2.pop()
            connect_cnt[midx] -= 1
            filled += 1
            ln2 -= 1
            for i in connect_ele[midx]:
                if ln1 > 0:
                    if ans[i-1] == 0:
                        ans[i-1] = num1.pop()
                        connect_cnt[i] -= 1
                        filled += 1
                        ln1 -= 1
                        pair_rem -=1
                else:
                    pm1()
        elif ln1 >= ln2 > 0:
            ans[midx-1] = num1.pop()
            connect_cnt[midx] -= 1
            filled += 1
            ln1 -= 1
            for i in connect_ele[midx]:
                if ln2 > 0:
                    if ans[i-1] == 0:
                        connect_cnt[i] -= 1
                        ans[i-1] = num2.pop()
                        filled += 1
                        ln2 -= 1
                        pair_rem -=1
                else:
                    pm1()
        else:
            pm1()

    num1.extend(num2)

    for i in range(n):
        if ans[i] == 0:
            ans[i] = num1.pop()

    print(*ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def mi():return map(int,input().split())
n,m=mi()
n=pow(2,n)-1
m=pow(2,m)-1

for i in range(n):
    if i%3==0:
        print("1"*m)
    else:
        print("1"+"001"*((m-1)//3)+"0"*(m-((m-1)//3)*3-1))

Submission status: Runtime Error

Solution code:
from collections import deque


n = int(input())

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


root = 0
visited = [-1] * n
def dfs(root):
    q = deque([root])
    visited[root] = 0
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v] != -1:
                continue
            else:
                visited[nxt_v] = (visited[v] + 1) % 2
                q.append(nxt_v)
dfs(0)
cnt0 = 0
cnt1 = 0
for i in range(n):
    if visited[i] == 0:
        cnt0 += 1
    else:
        cnt1 += 1

num1 = n // 3 
num2 = n // 3
num3 = n // 3
if n % 3 >= 1:
   num1 += 1
if n % 3 >= 2:
   num2 += 1
    
ans = [0] * n

set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
    if i % 3 == 0:
        set3.add(i)
    elif i % 3 == 1:
        set1.add(i)
    elif i % 3 == 2:
        set2.add(i)
        
if cnt0 <= num3:
    for i in range(n):
        if visited[i] == 0:
            ans[i] = pop.set3()
        else:
            if set1:
                ans[i] = pop.set1() 
            if set2:
                ans[i] = pop.set2()         
            if set3:
                ans[i] = pop.set3()  

elif cnt1 <= num3:
    for i in range(n):
        if visited[i] == 1:
            ans[i] = pop.set3()
        else:
            if set1:
                ans[i] = pop.set1() 
            if set2:
                ans[i] = pop.set2()         
            if set3:
                ans[i] = pop.set3()  
else:
    num147 = 0
    num258 = 0
    num369 = 0
    for i in range(n):
        if visited[i] == 0:
            num = num147 * 3 + 1
            if num > n:
                num = num369 * 3 + 3
                ans[i] = num
                if num > n:
                    error
                    exit()
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num # 1, 4, 7, 10, ...
            set1.remove(num)
            num147 += 1
        else:
            num = num258 * 3 + 2 
            if num > n:
                num = num369 * 3 + 3
                if num > n:
                    error
                    exit()
                ans[i] = num
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num # 2, 5, 8, 11, ...
            set2.remove(num)
            num258 += 1
     
    for i in range(n):
        if ans[i] == 0:
            if set1:
                ans[i] = set1.pop()
            elif set2:
                ans[i] = set2.pop()
            elif set3:
                ans[i] = set3.pop()
print(*ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

b=bfs(0)
m=b.index(max(b))
b=bfs(m)
ans=[0]*n
ans[m]=1
c=[0]*n
c[0]=1
x=4
for i in range(n):
  if b[i]%3==1:
    ans[i]=x
    c[x-1]=1
    x+=3
    if x>=n:
      break

ct=0
for i in range(n):
  if ans[i]==0:
    while c[ct]!=0 and ct<n:
      ct+=1
    c[ct]=1
    ans[i]=ct+1
for i in range(n):
  ans[i]=str(ans[i])
print(' '.join(ans))

Submission status: Runtime Error

Solution code:
N = int(input())

a = [None] * N
b = [None] * N

ps = {}
cs = {}
for i in range(N-1):
    a[i], b[i] = [int(n) for n in input().split()]
    if a[i] < b[i]:
        ps[b[i]] = a[i]
        if a[i] not in cs:
            cs[a[i]] = []
        cs[a[i]].append(b[i])
    else:
        ps[a[i]] = b[i]
        if b[i] not in cs:
            cs[b[i]] = []
        cs[b[i]].append(a[i])

dd = {}
def d(i, j):
    if i < j:
        p = i
        c = j
    elif i == j:
        return 0
    else:
        p = j
        c = i
    if (p, c) in dd:
        return dd[(p, c)]
    dd[(p, c)] = 1 + d(ps[c], p)
    return dd[(p, c)]

p = list(range(1, N+1))

for i in range(N-1):
    for j in range(i+1, N):
        if d(i + 1, j + 1) == 3:
            if (p[i] + p[j]) % 3 != 0 and (p[i] * p[j]) % 3 != 0:
                e = p[i]
                p[i] = p[i + 1]
                p[i + 1] = e

p = map(lambda a: str(a), p)
print(" ".join(p))

Submission status: Runtime Error

Solution code:
n = int(input())
a, b = [], []
for i in range(n):
  a1, b1 = list(map(int,input().split()))
  a.append(a1)
  b.append(b1)
  

for j in range(n):
  for w in range(n):
    roots=[ [] for i in range(n)]
    for a1 in range(a):
      roots[a1-1]+=[b[a.index[a1]-1]
      roots[b[a.index[a1]]-1]+=[a-1,c]
    dist=[-1]*n
    stack=[]
    stack.append(j)
    dist[j]=0
    while stack:
      label=stack.pop(-1)
      for i in roots[label]:
        if dist[i]==-1:
          dist[i]=dist[label]+1
          stack+=[i]
        if i==w:
          len =  dist[w]
                    
print('-1')

Submission status: Runtime Error

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,0,0]
    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: Runtime Error

Solution code:
# 久々の幅優先探索……

import queue

def main():

    n = int(input())
    edges = [list(map(int, input().split())) for _ in range(n-1)]
    num_0_mod_3 = n // 3
    num_2_mod_3 = (n+1) // 3
    num_1_mod_3 = (n+2) // 3


    def add_edge(u, v ):
        G[u].append(v)
        G[v].append(u)

    G = [[] for _ in range(n)] #グラフの隣接リスト表現
    for edge in edges:
        add_edge(edge[0]-1, edge[1]-1)

    num_distance_even = 0
    num_distance_odd = 0

    q = queue.Queue()
    q.put(0)

    distance = [-1] * n
    distance[0] = 0
    num_distance_even += 1

    for v in G[0]:
        q.put(v)

    while(q.qsize() > 0):
        now = q.get()
        for v in G[now]:
            if distance[v] >= 0:
                pass
            else:
                q.put(v)
                distance[v] = distance[now] + 1
                if (distance[v] & 1):
                    num_distance_odd += 1
                else:
                    num_distance_even += 1

    # print(distance)
    # print(num_distance_even, num_distance_odd)

    ans = [-1] * n

    index_one = 1
    index_two = 2
    index_zero = 3

    if num_distance_even >= num_1_mod_3 + num_2_mod_3:
        # evenに120 oddに0

        for i in range(n):
            if (distance[i] & 1) == 1:
                ans[i] = index_zero
                index_zero += 3
            else:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                elif (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3


    elif num_distance_odd >= num_1_mod_3 + num_2_mod_3:
        # evenに0 oddに012
        for i in range(n):
            if (distance[i] & 1) == 0:
                ans[i] = index_zero
                index_zero += 3
            else:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                elif (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3

    else:
    #     num_distance_even <= num_distance_odd * 2 and num_distance_odd <= num_distance_even * 2:
        # evenを2、oddを1、適宜0
        for i in range(n):
            if (distance[i] & 1) == 1:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3
            else:
                if (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3

    print(' '.join(list(map(str, ans))))


        """"ここに今までのコード"""

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
group = [[0], []]
idx = 1
stack = [0]
tmp = True
while tmp:
  tmp = []
  while stack:
    v = stack.pop()
    for u in edge[v]:
      if u not in group[idx ^ 1]:
        group[idx].append(u)
        tmp.append(u)
  idx ^= 1
one = n // 3 + int(n % 3 > 0)
two = n // 3 + int(n % 3 == 2)
three = n // 3
p = [0] * n
group.sort(key=len)
if len(group[0]) >= two:
  index3 = 1
  for i in range(two):
    v = group[0].pop()
    p[v] = 3 * i + 2
  while group[0]:
    v = group[0].pop()
    p[v] = 3 * index3
    index3 += 1
  for i in range(one):
    v = group[1].pop()
    p[v] = 3 * i + 1
  while group[1]:
    v = group[1].pop()
    p[v] = 3 * index3
    index3 += 1
else:
  print(-1)

Submission status: Runtime Error

Solution code:
N=int(input())
edges=[]
for i in range(N):
  A,B=map(int,input().split())
  edges.append([A,B])

def BFS(K,edges,N):
  lst=[]
  roots=[ [] for i in range(N)]
  for a,b in edges:
    roots[a-1]+=[(b-1,1)]
    roots[b-1]+=[(a-1,1)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
      if dist[i]==3:
         lst.append(roots[label][0])
      if dist[i]>3:
        break
        
  return lst

d=0
for i in range(n):
  d+=len(BFS(i+1,edges,N))
if d//2>((N//3)+(N-2)//3)//2:
  print('-1')
else:

Submission status: Runtime Error

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-1] = str(base[2])
            base[2] += 3
        else:
            ans[i-1] = 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: Runtime Error

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_himago[i]  > 0 or  tree_mago[par] - tree_child_num[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(1)
            else:
                assign[num] = (ind_1 ) * 3 + 1
                ind_1 += 1
        else:
            if ind_2 == lim_2: #割当が足りなくなったら
                print(-1)
                exit(1)
            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 += 2


print(*assign[1:])

Submission status: Runtime Error

Solution code:
import collections


N = int(input())
tree = {i: set() for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)

distance = {i: {d: list() for d in range(4)} for i in range(1, N + 1)}
visited = set()
for i in range(1, N + 1):
    if i in visited:
        continue
    queue = collections.deque([(0, i)])
    visited.add(i)
    while queue:
        d, cur = queue.popleft()
        if d > 3:
            continue
        for j in tree[cur]:
            if j not in visited:
                distance[i][d + 1].append(j)
                queue.append((d + 1, j))
                visited.add(j)
indices = []
for i, d in distance.items():
    if 3 in d:
        indices.extend([(i, j) for j in d[3]])
    if 1 in d and 2 in d:
        for j in d[1]:
            for k in d[2]:
                if k not in tree[j]:
                    indices.append((j, k))
del distance
del tree
del visited

count = collections.Counter([i for x in indices for i in x])
indices2 = collections.defaultdict(list)
for i, j in indices:
    if count[i] > count[j]:
        indices2[i].append(j)
    else:
        indices2[j].append(i)

del count
del indices


rest = {i: set() for i in range(3)}
for x in range(1, N + 1):
    rest[x % 3].add(x)

perm = [0] * N
for i, js in indices2.items():
    if rest[0] and (rest[1] or rest[2]):
        perm[i - 1] = rest[0].pop()
        for j in js:
            if rest[1]:
                perm[j - 1] = rest[1].pop()
            elif rest[2]:
                perm[j - 1] = rest[2].pop()
            elif rest[0]:
                perm[j - 1] = rest[0].pop()
            else:
                print(-1)
                break
    elif rest[1] and rest[2]:
        if len(rest[1]) > len(rest[2]):
            perm[i - 1] = rest[2].pop()
            for j in js:
                if rest[1]:
                    perm[j - 1] = rest[1].pop()
                elif rest[0]:
                    perm[j - 1] = rest[0].pop()
                else:
                    print(-1)
                    break
        else:
            perm[i - 1] = rest[1].pop()
            for j in js:
                if rest[2]:
                    perm[j - 1] = rest[2].pop()
                elif rest[0]:
                    perm[j - 1] = rest[0].pop()
                else:
                    print(-1)
                    break
    else:
        print(-1)
        break
else:
    rest = rest[1] | rest[2]
    if rest:
        for i in range(N):
            if perm[i] == 0:
                perm[i] = rest.pop()
    print(*perm)

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

import heapq

d = [10 ** 9 + 7] * N
d[0] = 0
q = [(0, 0)]
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_dst = dist + 1
        if dist_dst < d[dst]:
            d[dst] = dist_dst
            heapq.heappush(q, (dist_dst, dst))

n0 = []
n1 = []
n2 = []
for i in range(1, N + 1):
    if i % 3 == 0:
        n0.append(i)
    elif i % 3 == 1:
        n1.append(i)
    else:
        n2.append(i)

mods = [None] * N
for i in range(N):
    mods[i] = d[i] % 3
# print("#", ' '.join(map(str, mods)))

    
ans = [None] * N
i0 = i1 = i2 = 0
for i in range(N):
    if d[i] % 3 == 1:
        ans[i] = n1[i1]
        i1 += 1
    elif d[i] % 3 == 2:
        ans[i] = n2[i2]
        i2 += 1
    else:
        ans[i] = n0[i0]
        i0 += 1
    
print(' '.join(map(str, ans)))