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:
class Tree:
    def __init__(self, N):
        self.N = N # #vertices
        self.D = (self.N-1).bit_length() # #iterations in doubling
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def lca_initialize(self):
        self.dfs(0)
        self.doubling()
    
    def dfs(self, root):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the root.
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)
    
    def doubling(self):
        # O(N log N) time
        self.next = [[-1] * self.N for _ in range(self.D)]
        for v in range(self.N):
            self.next[0][v] = self.parent[v]
        for d in range(self.D - 1):
            for v in range(self.N):
                if self.next[d][v] != -1:
                    self.next[d + 1][v] = self.next[d][self.next[d][v]]
    
    def lca(self, u, v):
        # O(log N) time
        # the depth of v is set to be no less than that of u
        if self.depth[u] > self.depth[v]: u, v = v, u
        # find the ancestor of v with the same depth as that of u
        diff = self.depth[v] - self.depth[u]
        for i in range(diff.bit_length()):
            if diff & (1 << i): v = self.next[i][v]
        if u == v: return u
        for i in range(self.depth[u].bit_length() - 1, -1, -1):
            pu, pv = self.next[i][u], self.next[i][v]
            if pu != pv: u, v = pu, pv
        return self.next[0][u]

N = int(input())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(0)
d_odd, d_even = [], []
rem = [[] for _ in range(3)]
for i in range(N):
    if tr.depth[i] % 2 == 0: d_even.append(i)
    else: d_odd.append(i)
    rem[(i+1)%3].append(i+1)
P = [0] * N
flag = True
if len(d_odd) < len(d_even):
    for i in d_odd:
        if rem[2]:
            P[i] = rem[2].pop()
        elif rem[0]:
            P[i] = rem[0].pop()
        else:
            flag = False; break
    temp = rem[0] + rem[1]
    if flag:
        for i in d_even:
            if temp:
                P[i] = temp.pop()
            else:
                flag = False; break
else:
    for i in d_even:
        if rem[2]:
            P[i] = rem[2].pop()
        elif rem[0]:
            P[i] = rem[0].pop()
        else:
            flag = False; break
    temp = rem[0] + rem[1]
    if flag:
        for i in d_odd:
            if temp:
                P[i] = temp.pop()
            else:
                flag = False; break
print(*P if flag else -1)

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)
dfs(0,1)
if sum(perms) != n*(n+1)//2:
  perms = [0 for _ in range(n)]
  nums = [three+1,one,two]
  dfs(0,2)
  if sum(perms) != n*(n+1)//2:
    raise Exception
print(*perms)

Submission status: Runtime Error

Solution code:
#input
N = int(input())
Tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Tree[a].append(b)
    Tree[b].append(a)

# process
# 距離3の頂点を抽出
pair = []
for i in range(N):
    for j in Tree[i]:
        for k in Tree[j]:
            if k == i:
                continue
            for l in Tree[k]:
                if l == j or i > l:
                    continue
                pair.append((i,l))

# 順列を求める
def getAddNum(x, ans):
    t = 0
    for i in range(N):
        if (x+i)%3 == 0:
            t = i

    l = [x for x in range(t, N, 3)]
    for y in l:
        if not y in ans:
            return y

    return -1

def getMulNum(x, ans):
    l = []
    if x%3 == 0:
        l = [n for n in range(1, N+1)]

    else:
        l = [n*3 for n in range(1, N//3+1)]

    for y in l:
        if not y in ans:
            return y

    return -1

def getNextNum(x, ans):
    for y in range(x+1, N):
        if not y in ans:
            return y
    
ans = [-1 for _ in range(1, N+1)]
n = 1
for a, b in pair:
    a -= 1
    b -= 1
    if ans[a] == -1:
        ans[a] = n
        n = getNextNum(n, ans)
    
    t = getAddNum(ans[a], ans)
    if t > 0:
        ans[b] = t
    else:
        t = getMulNum(ans[a], ans)
        ans[b] = t

for i in range(N):
    if ans[i] == -1:
        ans[i] = n
        n = getNextNum(n, ans)

# output
# print(pair)
print(" ".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
print(*([3]*N))

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)

class Node:
    def __init__(self, node_id):
        self.id = node_id
        self.next = []


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

def main():
    n = int(input())
    nodes = [0] * (n+1)

    for i in range(1, n+1):
        nodes[i] = Node(i)

    for i in range(n-1):
        a, b = list(map(int,ipti().split()))
        nodes[a].next.append(b)
        nodes[b].next.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.next:
                    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][1]
        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 > 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()
        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 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)

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

Submission status: Runtime Error

Solution code:
from collections import deque

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)
root = -1

pa = {}
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:
def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    from itertools import permutations
    from collections import deque

    def bfs(G, s):
        dist = [-1 for _ in range(N)]
        que = deque()
        dist[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
        return dist

    ds = []
    for i in range(N):
        if 30 <= i:
            break
        ds.append(bfs(edge, i))
    # print(*ds, sep="\n")
    ans = []
    for i in range(N):
        if 5 < i:
            break
        for j, d in enumerate(ds[i]):
            if d == 3:
                ans.append((i, j))
    # print(ans)
    i = 0
    j = 0
    for p in permutations(range(1, N+1)):
        q = ans[0][0]
        r = ans[0][1]
        j += 1
        if 10**6 <= j:
            break
        if ((p[q] + p[r]) % 3 == 0 or (p[q] * p[r]) % 3 == 0)\
                and ((p[q] + p[r]) % 3 == 0 or (p[q] * p[r]) % 3 == 0):
            i += 1
            if i == 3:
                print(*p)
                return
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections


N = int(input())
tree = collections.defaultdict(set)
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))


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)


pool = set(range(1, N + 1))
three = set()
for x in pool:
    if x % 3 == 0:
        three.add(x)
pool -= three
perm = [0] * N
for i, js in indices2.items():
    if three and pool:
        perm[i - 1] = three.pop()
        for j in js:
            perm[j - 1] = pool.pop()

for i in range(N):
    if perm[i] == 0:
        perm[i] = pool.pop()
print(*perm)

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
mod_list = [0]*n
mod_list[0] = 1
tree = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append([a-1, b-1])
    tree[b-1].append([b-1, a-1])

already = [False]*n
not_yet = deque(tree[0])
judge = [False]*n

already[0] = True
flag = True
key = 0
count = 0
c0, c1, c2 = 0, 1, 0
while not_yet:
    key = not_yet[0]
    not_yet.popleft()
    p, q = key[0], key[1]
    if key == p:
        count += 1
        if count >= 3:
            judge[q] = True
    else:
        key = p
        count = 1
    already[q] = True
    mod_list[q] = mod_list[p]+1
    mod_list[q] %= 2
    if judge[q]:
        c0 += 1
    elif mod_list[q]:
        c1 += 1
    else:
        c2 += 1
    
    for value in tree[q]:
        if already[value[1]]:
            continue
        else:
            not_yet.append(value)

ans = [0]*n
mod_0 = [int(x) for x in range(3, n+1, 3)]
mod_1 = [int(x) for x in range(1, n+1, 3)]
mod_2 = [int(x) for x in range(2, n+1, 3)]

if c1 < c2:
    mod_1, mod_2 = mod_2, mod_1

k0, k1, k2 = 0, 0, 0
for i in range(n):
    if judge[i]:
        ans[i] = mod_0[k0]
        k0 += 1
        continue
    if mod_list[i] == 1:
        if k1 == len(mod_1):
            ans[i] = mod_0[k0]
            k0 += 1
            continue
        ans[i] = mod_1[k1]
        k1 += 1
        continue
    else:
        if k2 == len(mod_2):
            ans[i] = mod_0[k0]
            k0 += 1
            continue
        ans[i] = mod_2[k2]
        k2 += 1
        continue
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)]
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)

ptns = [
    [0,1,1,0,2,2],
    [0,1,2,0,2,1],
    [0,2,1,0,1,2],
    [0,2,2,0,1,1],
    [2,0,1,1,0,2],
    [1,0,1,2,0,2],
    [2,0,2,1,0,1],
    [1,0,2,2,0,1],
    [2,2,0,1,1,0],
    [2,1,0,1,2,0],
    [1,2,0,2,1,0],
    [1,1,0,2,2,0]
]
mem = [[[] for _ in range(3)] for _ in range(12)]
for i,d in enumerate(depth):
    for k,ptn in enumerate(ptns):
        mem[k][ptn[d%6]].append(i)

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

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
n = int(readline())

graph = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    graph[a].append(b)
    graph[b].append(a)
 
#親のノードに子を入れてくdfs
AB = []
def bfs(i): #長さ3までi=3まで
    queue = deque([[i,0]])
    visited = []
    while queue:
        x,l = queue.popleft()
        if l < 3:
            for j in graph[x]:
                if not j in visited:
                    queue.append([j,l+1])
            visited.append(x)
        else:
            if i < x:
                AB.append([i,x])
            visited.append(x)
for i in range(1,n+1):
    bfs(i)
graph = [[] for _ in range(n+1)] #隣接リスト
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

#親のノードに子を入れてくdfs
stack = [AB[0][0]] #グラフに組み込まれた適当な値を入れる
parent = [0]*(n+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in graph[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

ans = [0]*(n+1)

t0 = deque([i*3 for i in range(1,n//2)])
t1 = deque([1+i*3 for i in range(0,n//2)])
t2 = deque([2+i*3 for i in range(0,n//2)])

for x in order: #親
    if parent[x] == 0:
        ans[x] = t1.pop()
    else:
        if ans[parent[x]]%3 == 0: #ans[parent[x]] != 0 and ←決まってる？
            if len(t1)!=0:
                ans[x] = t1.pop()
            elif len(t2)!=0:
                ans[x] = t2.pop()
            elif len(t0) != 0:
                ans[x] = t0.pop()
        elif ans[parent[x]]%3 == 1:
            if len(t2) != 0:
                ans[x] = t2.pop()
            elif len(t0) != 0:
                ans[x] = t0.pop()
            else:
                print(-1)
                exit()
        else:
            if len(t1) != 0:
                ans[x] = t1.pop()
            elif len(t0) != 0:
                ans[x] = t0.pop()
            else:
                print(-1)
                exit()

nokori = t0+t1+t2
j = 0
for i in range(1,n+1):
    if ans[i] == 0:
        ans[i] = nokori[j]
        j += 1
print(*ans[1:])

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)

    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])])]
    # 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)]
    ANS = [0]*N
    S = [ (L[0]+L[3], 0), (L[1]+L[4],1), (L[2]+L[5],2)]
    S.sort(reverse=True)
    for j in range(3):
        i = S[j][1]
        x = i
        y = i+3
        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 = [list(map(int, input().split())) for _ in range(n - 1)]

from collections import defaultdict
graph = defaultdict(list)
for i in range(n - 1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * n
def dfs(cur, _dist):
    dist[cur] = _dist
    for target in graph[cur]:
        if dist[target] == -1:
            dfs(target, _dist + 1)

dfs(0, 0)

tmp = [set(), set(), set()]
for i in range(n):
    if dist[i] % 6 in [0, 3]:
        tmp[0].add(i)
    elif dist[i] % 6 in [1, 5]:
        tmp[1].add(i)
    else:
        tmp[2].add(i)

tmp2 = []
for i in range(3):
    tmp2.append([len(tmp[i]), tmp[i]])
tmp2.sort(reverse=True)

n_0 = n // 3
n_1 = (n + 2) // 3
n_2 = (n + 1) // 3
p0 = [i * 3 + 3 for i in range(n_0)]
p1 = [i * 3 + 1 for i in range(n_1)]
p2 = [i * 3 + 2 for i in range(n_2)]

ans = [0] * n

# 0
tmp22 = list(tmp2[2][1])
for i in range(tmp2[2][0]):
    ans[tmp22[i]] = p0.pop()
left_0 = n_0 - tmp2[2][0]

# 1
tmp21 = list(tmp2[1][1])
for i in range(min(tmp2[1][0], n_1)):
    ans[tmp21[i]] = p1.pop()
left_1 = max(0, n_1 - tmp2[1][0])

# 2
tmp20 = list(tmp2[0][1])
lefts = [i * 3 + 2 for i in range(n_2)]
for idx in tmp20:
    visited = set([idx])
    cur = set([idx])
    for i in range(3):
        curnew = set()
        for j in cur:
            visited.add(j)
            for target in graph[j]:
                if target not in visited:
                    curnew.add(target)
        cur = curnew

    f = True
    for c in cur:
        if c in tmp2[1][1]:
            f = False
            break

    if not f:
        # 2 or 0
        if p2:
            ans[idx] = p2.pop()
        else:
            ans[idx] = p0.pop()
    else:
        if p2:
            ans[idx] = p2.pop()
        elif p1:
            ans[idx] = p1.pop()
        else:
            ans[idx] = p0.pop()

print(ans)

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)

class Node:
    def __init__(self, node_id):
        self.id = node_id
        self.next = []

def main():
    n = int(input())
    nodes = [0] * (n+1)

    for i in range(1, n+1):
        nodes[i] = Node(i)

    for i in range(n-1):
        a, b = list(map(int,ipti().split()))
        nodes[a].next.append(b)
        nodes[b].next.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.next:
                    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][1]
        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)

    impossible = False

    while pair_rem > 0:
        midx = num_connect_cnt.most_common()[0][1]
        if ln2 > 0:
            ans[midx-1] = num2.pop()
            filled += 1
            ln2 -= 1
            for i in num_connect_ele:
                if ln1 > 0:
                    ans[i-1] = num1.pop()
                    filled += 1
                    ln1 -= 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)


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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections


N = int(input())
tree = collections.defaultdict(set)
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))


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)


pool = set(range(1, N + 1))
three = set()
for x in pool:
    if x % 3 == 0:
        three.add(x)
pool -= three
perm = [0] * N
for i, js in indices2.items():
    if three and pool:
        perm[i - 1] = three.pop()
        for j in js:
            perm[j - 1] = pool.pop()
    else:
        print(-1)
        break
else:
    for i in range(N):
        if perm[i] == 0:
            perm[i] = pool.pop()
    print(*perm)

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)

dfs(0,1)
if sum(perms) != n*(n+1)//2:
  perms = [0 for _ in range(n)]
  dfs(0,2)
print(*perms)

Submission status: Runtime Error

Solution code:
class Edges():
    def __init__(self, n):
        self.eds = [[]]
        self.k = [0] * n
    def add(self, x, y):
        self.eds.append([min([x, y]), max([x, y])])
        self.k[x - 1] += 1
        self.k[y - 1] += 1
    def search(self, x):
        yArray = []
        for y in range(n):
            if(x == y):
                pass
            elif([min([x, y]), max([x, y])] in self.eds):
                yArray.append(y)
            else:
                pass
        return yArray
    def maxK(self):
        return max(self.k)
        


N = int(input())
edges = Edges(N)
for i in range(N - 1):
    n1, n2 = map(int,input().split())
    edges.add(n1, n2)
if(edges.maxK() > n - 1):
    print(' '.join(['3'] * N))
else:
    print(-1)