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:
from heapq import heappop, heappush
from collections import deque


class Tree():
    def __init__(self,n,edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append((e[1] - 1, 1))
            self.tree[e[1] - 1].append((e[0] - 1, 1))
    def setroot(self,root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.distance = [None for _ in range(self.n)]
        self.distance[root] = 0
        stack = [root]
        while stack:
            node = stack.pop()
            for adj,cost in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node]+1
                    self.distance[adj] = self.distance[node]+cost
                    stack.append(adj)
    def diam(self):
        u = self.distance.index(max(self.distance))
        dist_u = [None for _ in range(N)]
        dist_u[u] = 0
        stack = [u]
        while stack:
            node = stack.pop()
            for adj,cost in self.tree[node]:
                if dist_u[adj] is None:
                    dist_u[adj] = dist_u[node]+cost
                    stack.append(adj)
        d = max(dist_u)
        v = dist_u.index(d)
        return d,u,v
    def construct_lca(self):
        L = (self.n-1).bit_length()
        self.k_parent = [self.parent]
        prev = self.parent
        for k in range(L):
            array = [0 for _ in range(self.n)]
            for i in range(self.n):
                if prev[i] == -1: continue
                array[i] = prev[prev[i]]
            self.k_parent.append(array)
            prev = array
    def lca(self,u,v):
        d = self.depth[v]-self.depth[u]
        if d < 0: u,v,d = v,u,-d
        for k in self.k_parent:
            if d & 1: v = k[v]
            d >>= 1
        if u == v: return u
        for k in reversed(self.k_parent):
            pu,pv = k[u],k[v]
            if pu != pv: u,v = pu,pv
        return self.k_parent[0][u]
    def dist(self,u,v):
        l = self.lca(u,v)
        return self.distance[u]+self.distance[v]-2*self.distance[l]

      
n = int(input())
N = n
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)


t = Tree(n, info)
t.setroot(0)
t.construct_lca()
d,u,v = t.diam()
distance2 = []
for i in range(n):
    distance2.append(max(t.dist(i,u), t.dist(i,v)))


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)
for i in range(n):
    if distance2[i] < 3:
        visited[i] = -1

cnt1 = n // 3 
cnt2 = n // 3
cnt3 = n // 3
if n % 3 >= 1:
   cnt1 += 1
if n % 3 >= 2:
   cnt2 += 1

# print(visited)
# print(cnt1, cnt2, cnt3)

cnt = [0, 0]
for i in range(n):
    if visited[i] == 0:
        cnt[0] += 1
    elif visited[i] == 1:
        cnt[1] += 1

#if cnt[0] >= cnt[1]:
#    pass
#else:
#    for i in range(n):
#        if visited[i] == 0:
#            visited[i] = 1
#        elif visited[i] == 1:
#            visited[i] = 0

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)

ans = [0] * n
num147 = 0
num258 = 0
num369 = 0
for i in range(n):
    if visited[i] == -1:
        continue
    elif 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()
        else:
            error
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)

x1, x2, x3 = [], [], []
for n in range(1, N + 1):
    if n % 3 == 1:
        x1.append(n)

    elif n % 3 == 2:
        x2.append(n)

    elif n % 3 == 0:
        x3.append(n)


ans = [-1] * N


def allocate(i, pop_target):
    if pop_target == 1:
        if x1:
            ans[i] = x1.pop()
        else:
            ans[i] = x3.pop()

    else:
        if x2:
            ans[i] = x2.pop()
        else:
            ans[i] = x3.pop()


def bfs(s):
    que = deque([(s, 0)])
    pop_target = 1 if len(x1) >= len(x2) else 2

    while que:
        n, depth = que.pop()
        if depth == 2:
            continue

        allocate(n, pop_target)
        for to in T[n]:
            if ans[to] > 0:
                continue
            que.appendleft((to, depth + 1))


for n in range(N):
    if ans[n] > 0:
        continue
    bfs(n)

print(*ans, sep=' ')

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)



    # oned = deque([ i*3+1 for i in range(one+1)])
    # twod = deque([ i*3+2 for i in range(two+1)])
    L = [ len(F[i]) for i in range(6)]
    check = True
    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[1] > L[j]:
                    count[1] -= L[j]
                else:
                    c = L[j] - count[1]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c

                if count[1] > L[j+3]:
                    count[1] -= L[j+3]
                else:
                    c = L[j+3] - count[1]
                    if count[0] < c:
                        check = False
                        break
                    count[0] -= c
            if check:
                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 = q[j]
        x = i
        y = i+3
        if p[i] == 1:
            x, y = y, x
        # if L[x] > L[y]:
        #     x, y = y, x
        if count[0] < count[1]:
            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()
            else:
                count[0] -= 1
                ANS[w] = ds[0].popleft() 

        for w in F[y]:
            if ds[t]:
                count[t] -= 1
                ANS[w] = ds[t].popleft()
            else:
                count[0] -= 1
                ANS[w] = ds[0].popleft() 
               
    print( " ".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import networkx as nx
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import math

def main():
    n = int(input())
    num_list = []
    for _ in range(n-1):
        num_list.append(list(map(int,input().split())))

    G = nx.Graph()
    nodes = [i+1 for i in range(n)]
    G.add_nodes_from(nodes)
    G.add_edges_from(num_list)
    adj_mat = nx.to_numpy_matrix(G)
    # print(adj_mat)

    tmp_list = []
    is_find = False

    for i in range(n):
        if is_find:
            break
        dist_list = dijkstra(np.array(adj_mat), indices=i, directed=False, unweighted=True)
        for j in range(n):
            if math.ceil(dist_list[j]) == 3:
                tmp_list.append(j+1)
                is_find = True

    ans_list = [0] * n

    ans_list[i-1] = 2

    for i in tmp_list:
        ans_list[i-1] = 3

    for i in range(n):
        if i == n-1:
            print(ans_list[i])
            break
        print(ans_list[i],end=' ')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
ab = [read_int() for _ in range(N - 1)]

adj_list = defaultdict(list)
# adj_list: key...int start, value... [] ends
for e in ab:
    adj_list[e[0]].append(e[1])
    adj_list[e[1]].append(e[0])
# print(adj_list)

res = []
def solve():
    ans = [i for i in range(1, N + 1)]
    for e in range(1, N + 1):
        # if e != 2:
        #     continue
        rec(e, 0, [])
    for r in res:
        a1 = ans[r[0] - 1]
        a2 = ans[r[1] - 1]
        if (a1 + a2) % 3 != 0 and (a1 * a2) % 3 != 0:
            swapped = False
            for i in range(2, N, 3):
                if ans[i] == i + 1:
                    ans[i], ans[r[1] - 1] = ans[r[1] - 1], ans[i]
                    swapped = True
                if swapped: break
            if not swapped: return -1
    return ans

def rec(e, i, vis):
    vis.append(e)
    if i == 3 and vis[0] < e:
        # for adj in adj_list[e]:
            # res.append([vis[0], adj])
            # print([vis[0], adj], vis)
        res.append([vis[0], e])

        return
    for adj in adj_list[e]:
        if not (adj in vis):
            # print(adj, i, vis)
            rec(adj, i + 1, vis)


if __name__ == "__main__":
    ans = solve()
    print(' '.join(map(str,ans)))
    # print(res)

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 = []
        while que:
            current_id, dist = que.popleft()
            seen.append(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))

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

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

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

    while num3 and pair_rem>0:
        midx = num_connect_cnt.most_common()[0][0]
        ans[midx-1] = num3.pop()
        filled += 1
        pair_rem -= num_connect_cnt[midx]
        num_connect_cnt[midx] = 0
        for idx in num_connect_ele[midx]:
            num_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 = num_connect_cnt.most_common()[0][0]

        if ln2 > ln1 > 0:
            ans[midx-1] = num2.pop()
            filled += 1
            ln2 -= 1
            for i in num_connect_ele[midx]:
                if ln1 > 0:
                    ans[i-1] = num1.pop()
                    filled += 1
                    ln1 -= 1
                    pair_rem -=1
                else:
                    pm1()
        elif ln1 >= ln2 > 0:
            ans[midx-1] = num1.pop()
            filled += 1
            ln1 -= 1
            for i in num_connect_ele[midx]:
                if ln2 > 0:
                    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:
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 = collections.defaultdict(lambda: collections.defaultdict(list))
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()
        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


pool = set(range(1, N + 1))
three = set()
for x in pool:
    if x % 3 == 0:
        three.add(x)
pool -= three
rest = collections.defaultdict(set)
for x in pool:
    rest[x % 3].add(x)

perm = [0] * N
for i, js in indices2.items():
    if three and pool:
        perm[i - 1] = three.pop()
        for j in js:
            if rest[1]:
                perm[j - 1] = rest[1].pop()
            elif rest[2]:
                perm[j - 1] = rest[2].pop()
            elif three:
                perm[j - 1] = three.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()
                else:
                    print(-1)
                    break
        else:
            perm[i - 1] = rest[1].pop()
            for j in js:
                if rest[2]:
                    perm[j - 1] = rest[2].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())
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]


ansl = []
for d in dist:
    if d % 2 == 0:
        if numbers1:
            ansl.append(numbers1.pop())
        else:
            ansl.append(numbers3.pop())
    else:
        if numbers2:
            ansl.append(numbers2.pop())
        else:
            ansl.append(numbers3.pop())
for a in ansl:
    print(a)

Submission status: Runtime Error

Solution code:
import queue 
def minEdgeBFS(edges, u, v, n): 
    visited = [0] * n 
    distance = [0] * n 
    Q = queue.Queue() 
    distance[u] = 0
    Q.put(u) 
    visited[u] = True
    while (not Q.empty()): 
        x = Q.get() 
        for i in range(len(edges[x])): 
            if (visited[edges[x][i]]): 
                continue
            distance[edges[x][i]] = distance[x] + 1
            Q.put(edges[x][i]) 
            visited[edges[x][i]] = 1
    return distance[v] 

def addEdge(edges, u, v): 
    edges[u].append(v) 
    edges[v].append(u) 


n = int(input())
edges = [[] for i in range(n+1)] 
for i in range(n-1):
    a,b=map(int,input().split())
    addEdge(edges, a, b)
lis=[0 for i in range(5)]
f=0
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if(minEdgeBFS(edges, i, j, n+1)==3):
            lis[i-1]=2
            if(f==1):
                lis[j-1]=3
            else:
                lis[j-1]=4
            f=1
if(f==0):
    print(-1)
else:
    tmp=[]
    for i in range(1,6):
        if(i not in lis):
            tmp.append(i)
    j=0
    for i in range(5):
        if(not lis[i]):
            lis[i]=tmp[j]
            j+=1
    print(*lis)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
graph = {i:[] for i in range(n)}
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
  
one = n//3 + bool(n%3)
two = n//3 + bool(n%3>1)
three = n//3
nums = [three+1,one,two]
perms = [0 for i in range(n)]



def dfs(i,n):
  global nums
  perms[i] = (nums[n]-1)*3 + n
  nums[n] -= 1 
  for node in graph[i]:
    if perms[node] == 0:
      next_n = (3-n)%3
      if nums[next_n] == 0:
        dfs(node,0)
      else:
        dfs(node,next_n)


for i in range(n):
  dfs(i,1)
  if sum(perms) == n*(n+1)//2:
    break
  perms = [0 for _ in range(n)]
  nums = [three+1,one,two]
print(*perms)

Submission status: Runtime Error

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


def dist_3(i):
    q = deque([i])
    pair = []
    for a in G[i]:
        for b in G[a]:
            for c in G[b]:
                pair.append(c)
    return pair


ans = list(range(1, n+1))
idx = sorted(range(n), key=lambda x:deg[x])
for i in range(n//3):
    ans[idx[i]], ans[(i+1)*3] = ans[(i+1)*3], ans[idx[i]]
print(*ans)

Submission status: Runtime Error

Solution code:
a, b, m = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = min(A) + min(B)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
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)



    # oned = deque([ i*3+1 for i in range(one+1)])
    # twod = deque([ i*3+2 for i in range(two+1)])
    L = [ len(F[i]) for i in range(6)]
    
    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 j in range(3):
            if p[j] == 0:
                s = 1
                t = 2
            else:
                s = 2
                t = 1
            
            if count[1] > L[j]:
                count[1] -= L[j]
            else:
                c = L[j] - count[1]
                if count[0] < c:
                    check = False
                    break
                count[0] -= c

            if count[1] > L[j+3]:
                count[1] -= L[j+3]
            else:
                c = L[j+3] - count[1]
                if count[0] < c:
                    check = False
                    break
                count[0] -= c
        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 i in range(3):
        x = i
        y = i+3
        if p[i] == 1:
            x, y = y, x
        # if L[x] > L[y]:
        #     x, y = y, x
        if count[0] < count[1]:
            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()
            else:
                count[0] -= 1
                ANS[w] = ds[0].popleft() 

        for w in F[y]:
            if ds[t]:
                count[t] -= 1
                ANS[w] = ds[t].popleft()
            else:
                count[0] -= 1
                ANS[w] = ds[0].popleft() 
               
    print( " ".join( map( str, ANS)))
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())

AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))

kouho = []
for i in range(len(AB)):
    for i2 in AB[i]:
        for i3 in i2:
            for i4 in AB[i3]:
                for i5 in i4:
                    for i6 in AB[i5]:
                        if (i + i6) % 3 == 0 or (i * i6) % 3 == 0:
                            kouho.append([i, i6])

jyunretu_kouho = []
for i in range(len(kouho)):
    try:
        if kouho[i][1] == kouho[i + 1][0]:
            jyunretu_kouho.append(kouho[i][0],kouho[i][1],kouho[i + 1][0],kouho[i + 1][1])
    except:
        pass

Submission status: Runtime Error

Solution code:
from collections import deque,defaultdict

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

pa = defaultdict(int)
pa[-1] = -1
pa[0] = -1
que = deque([(-1,0)])
while que:
    pre,now = que.popleft()
    for child in G[now]:
        if child == pre:continue
        pa[child] = now
        que.append((now,child))

Graph = []
for i in range(n):
    if pa[pa[i]] != -1:
        Graph.append(G[pa[pa[i]]].copy())
        Graph[-1].remove(pa[i])
    else:
        Graph.append([])
G = [[] for _ in range(n)]
for i in range(n):
    for j in Graph[i]:
        G[i].append(j)
        G[j].append(i)
#print(G)
ans = [-1 for i in range(n)]
num = [[len(G[i]),i] for i in range(n)]
num.sort(reverse=True)
#print(num)
i = 1
while 3*i <= n:
    ans[num[i-1][1]] = 3*i
    i += 1


use = [1, 2]
for i in range(n):
    #print(ans)
    if ans[i] != -1: continue
    queue = deque([])
    if use[0] + 1 <= max(use[1], n):
        ans[i] = use[0]
        use[0] += 3
        queue.append((i,1))
    elif use[1] <= max(use[0] + 1, n):
        ans[i] = use[1]
        use[1] += 3
        queue.append((i,2))
    while queue:
        now,num = queue.popleft()
        for to in G[now]:
            if ans[to] != -1:continue
            if num == 1:
                if use[1] > n:
                    print(-1)
                    exit()
                ans[to] = use[1]
                use[1] += 3
                queue.append((to,2))
            else:
                if use[0] > n:
                    print(-1)
                    exit()
                ans[to] = use[0]
                use[0] += 3
                queue.append((to,1))

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5+1)

def cur(p):
    for i in x[p]:
        if rank[i]==-1:
            rank[i]=rank[p]+1
            par[i]=p
            cur(i)


n=int(input())
x=[[] for i in range(n)]

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

rank=[-1 for i in range(n)]
rank[0]=0
par=[-1 for i in range(n)]

cur(0)
M=max(rank)
x=[[] for i in range(M+1)]

q=[0,0]
r=[n//3,n//3,n//3]
if n%3>0: r[1]+=1
if n%3>1: r[2]+=1
tmp1,tmp2,tmp3=1,2,3

for i in range(n):
    q[rank[i]%2]+=1
    x[rank[i]].append(i)
ans=[-1 for i in range(n)]


if q[0]>r[0]+r[1] or q[1]>r[0]+r[2]:
    if q[0]>r[0]+r[2] or q[1]>r[0]+r[1]:
        print(-1)
        sys.exit()
    else:
        tmp1,tmp2=2,1


for i in range(M+1):
    if i%2==0:
        for p in x[i]:
            if tmp1<=n:
                ans[p]=tmp1
                tmp1+=3
            else:
                ans[p]=tmp3
                tmp3+=3
    else:
        for p in x[i]:
            if tmp2<=n:
                ans[p]=tmp2
                tmp2+=3
            else:
                ans[p]=tmp3
                tmp3+=3


for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
n = 2 ** N - 1
m = 2 ** M - 1
A = np.empty((n, m))
for i in range(n):
    for j in range(m):
        x = (i + j) % 2
        if x == 0:
            A[i, j] = 1
        else:
            A[i, j] = 0
for i in A:
  print(*i)