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 sys
input = sys.stdin.readline
 
N = int(input())
E = [[] for _ in range(N+1)]

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)

dist = [-1] * (N+1)
dist[1] = 0
q = [1]

while q:
	cp = q.pop(0)
	for np in E[cp]:
		if dist[np] == 0:
			dist[np] = dist[cp] + 1
			q.append(np)

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

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

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += 1
                self.dfs(v)
                self.depth -= 1

        self.colors[u] = self.BLACK


tree = Tree(adj)
tree.dfs(0)

ev = [i for i, e in enumerate(tree.depths) if e % 2 == 0]
od = [i for i, e in enumerate(tree.depths) if e % 2]

l_ev = len(ev)
l_od = len(od)

mod0 = [e for e in range(1, n + 1) if e % 3 == 0]
mod1 = [e for e in range(1, n + 1) if e % 3 == 1]
mod2 = [e for e in range(1, n + 1) if e % 3 == 2]

ans = [0] * n


def f(li1, li2):
    while li1 and li2:
        i = li1.pop()
        num = li2.pop()
        ans[i] = num


if l_ev > n / 3 and l_od > n / 3:
    f(ev, mod1)
    f(od, mod2)
    f(ev, mod0)
    f(od, mod0)

elif l_ev <= n / 3:
    f(ev, mod0)
    f(od, mod0)
    f(od, mod1)
    f(od, mod2)

else:
    f(od, mod0)
    f(ev, mod0)
    f(ev, mod1)
    f(ev, mod2)

print(*ans)

Submission status: Runtime Error

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
dfs(root, 0)

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

from collections import deque
q0 = deque(i for i in range(1,N+1) if i%3 == 0)
q1 = deque(i for i in range(1,N+1) if i%3 == 1)
q2 = deque(i for i in range(1,N+1) if i%3 == 2)

even_depth = len(list(filter(lambda d: d%2 == 0, depth)))
odd_depth = len(list(filter(lambda d: d%2 != 0, depth)))

if even_depth > N//3 and odd_depth > N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            if len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q0.popleft()
        else:
            if len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
elif even_depth <= N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q0.popleft()
        else:
            if len(q0) > 0:
                res[i] = q0.popleft()
            elif len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q2.popleft()
else:
    for i, d in enumerate(depth):
        if d%2 == 1:
            res[i] = q0.popleft()
        else:
            if len(q0) > 0:
                res[i] = q0.popleft()
            elif len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q2.popleft()


print_l(res)

Submission status: Runtime Error

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

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)
 
color = [0] * (n+1) #color[i]:点iの色(1 or -1)。但し塗られていないときは0とする

def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(g[v])):
        if color[ g[v][i] ] == c:
            return False
        elif color[ g[v][i] ] == 0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
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 i in range(n):
    if color[i] == 0:
        res = f(i,1)
black = 0
for i in color[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if color[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if color[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])

Submission status: Runtime Error

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
dfs(root, 0)

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

from collections import deque
q0 = deque(i for i in range(1,N+1) if i%3 == 0)
q1 = deque(i for i in range(1,N+1) if i%3 == 1)
q2 = deque(i for i in range(1,N+1) if i%3 == 2)

even_depth = len(list(filter(lambda d: d%2 == 0, depth)))
odd_depth = len(list(filter(lambda d: d%2 != 0, depth)))

if even_depth >= N//3 and odd_depth >= N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            if len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q0.popleft()
        else:
            if len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
elif even_depth < N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q0.popleft()
        else:
            if len(q0) > 0:
                res[i] = q0.popleft()
            elif len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q2.popleft()
else:
    for i, d in enumerate(depth):
        if d%2 == 1:
            res[i] = q0.popleft()
        else:
            if len(q0) > 0:
                res[i] = q0.popleft()
            elif len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q2.popleft()


print_l(res)

Submission status: Runtime Error

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

def dfs(i,col):
    nex=[]
    for k in x[i]:
        if c[k]==-1:
            c[k]=col
            nex.append(k)
    for k in nex:
        if col==2:
            dfs(k,1)
        else:
            dfs(k,2)

dfs(0,c[0])
d=[]
e=[]
f=[]
for i in range(n):
    if c[i]==1:
        x=n//3+(0 if n%3==0 else 1)
        if len(d)==x:
            f.append(i+1)
        else:
            d.append(i+1)
    else:
        x=n//3+(1 if n%3==2 else 0)
        if len(e)==x:
            f.append(i+1)
        else:
            e.append(i+1)
ans=[-1]*n
g=[d,e,f]
g.sort(key=lambda x:len(x),reverse=True)
d,e,f=g
for i in range(n):
    if i%3==0:
        ans[i]=d[i//3]
    elif i%3==1:
        ans[i]=e[i//3]
    else:
        ans[i]=f[i//3]
print(" ".join(map(str,ans)))

Submission status: Runtime Error

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
dfs(root, 0)

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

from collections import deque
q0 = deque([i for i in range(1,N+1) if i%3 == 0 ])
q1 = deque([i for i in range(1,N+1) if i%3 == 1 ])
q2 = deque([i for i in range(1,N+1) if i%3 == 2 ])

even_depth = len(list(filter(lambda d: d%2 == 0, depth)))
odd_depth = len(list(filter(lambda d: d%2 != 0, depth)))

if even_depth >= N//3 and odd_depth >= N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            if len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q0.popleft()
        else:
            if len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
elif even_depth < N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q0.popleft()
        else:
            if len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q2.popleft()
else:
    for i, d in enumerate(depth):
        if d%2 == 1:
            res[i] = q0.popleft()
        else:
            if len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q2.popleft()


print_l(res)

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
    oe_index[oe] += [i]
    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)
oe_index = [[], []]
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)
even_len = len(oe_index[0])
odd_len = len(oe_index[1])
if even_len > N//3 and odd_len > N//3:
    for i, oe in enumerate(ans):
        if base[oe] > N:
            ans[i] = str(base[2])
            base[2] += 3
        else:
            ans[i] = str(base[oe])
            base[oe] += 3
elif even_len <= N//3:
    for i in oe_index[0]:
        ans[i] = str(base[2])
        base[2] += 3
    for i in oe_index[1]:
        if base[0] <= N:
            ans[i] = str(base[0])
            base[0] += 3
        else:
            ans[i] = str(base[1])
            base[1] += 3
elif odd_len <= N//3:
    for i in oe_index[1]:
        ans[i] = str(base[2])
        base[2] += 3
    for i in oe_index[0]:
        if base[0] <= N:
            ans[i] = str(base[0])
            base[0] += 3
        else:
            ans[i] = str(base[1])
            base[1] += 3
print(' '.join(ans))

Submission status: Runtime Error

Solution code:
import sys
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

impo = [0]*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
    if judge[q]:
        c0 += 1
    elif mod_list[q]%2 == 1:
        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)]

depth = max(mod_list)
if depth == 2:
    print(*[int(x) for x in range(1, n+1)])
    sys.exit()

k0, k1, k2 = 0, 0, 0
T = False
if c1 < len(mod_0):
    T = True
    for i in range(n):
        if mod_list[i] == 1:
            ans[i] = [k0]
            k0 += 1

elif c2 < len(mod_0):
    T = True
    for i in range(n):
        if mod_list[i] == 0:
            ans[i] = [k0]
            k0 += 1

if T:
    i == 0
    while k0 < len(mod_0):
        if ans[i] == 0:
            ans[i] = mod_0[i]
            k0 += 1
        i += 1
    for j in range(len(mod_1)):
        if ans[i] == 0:
            ans[i] = mod_1[j]
        i += 1
    for j in range(len(mod_2)):
        if ans[i] == 0:
            ans[i] = mod_2[j]
        i += 1
    print(*ans)
    sys.exit()
for i in range(n):
    if ans[i] != 0:
        continue
    if judge[i]:
        ans[i] = mod_0[k0]
        k0 += 1
        continue
    if mod_list[i]%2 == 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:
"""
C - ThREE
"""

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

for i in range(n):
    for j in range(n):
        if i == j:
            uzaklik_list[i].append(0)
        else:
            if j in komsu_list[i]:
                uzaklik_list[i].append(1)
            else:
                uzaklik_list[i].append(200000)

for i in range(n):
    for j in range(n):
        if uzaklik_list[i][j] == 0:
            pass
        else:
            for m in range(n):
                uzaklik_list[i][m] = min(uzaklik_list[i][j]+uzaklik_list[j][m], uzaklik_list[i][m])

p_list = []

for i in range(int(n/2)):
    for j in range(n):
        if uzaklik_list[i][j]==3:
            p_list.append([i, j])

from itertools import permutations
l = list(permutations(range(1, n+1)))
liste = []
for eleman in l:
    new = ''.join(str(i) for i in eleman)
    liste.append(new)

if not p_list:
    print(-1)
else:
    for sayi in liste:
        flag = True
        for durum in p_list:
            if (int(sayi[durum[0]])+int(sayi[durum[1]])) % 3 == 0 or (int(sayi[durum[0]])*int(sayi[durum[1]])) % 3 == 0:
                pass
            else:
                flag = False
        if flag:
            print(sayi)
            break
if flag is False:
    print(-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()
    for i in range(n):
        if visited[i] == 1:
            if set1:
                ans[i] = pop.set1() 
            elif set2:
                ans[i] = pop.set2()         
            elif set3:
                ans[i] = pop.set3()  

elif cnt1 <= num3:
    for i in range(n):
        if visited[i] == 1:
            ans[i] = pop.set3()
    for i in range(n):
        if visited[i] == 0:
            if set1:
                ans[i] = pop.set1() 
            elif set2:
                ans[i] = pop.set2()         
            elif 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:
                    print(-1)
                    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:
                    print(-1)
                    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:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
    exit()


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        for node in self.linked:
            if node is parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

# usokaihou
import random

root = nodes[random.randint(1, N)]
root.set_rank(None, 1)

group = [[], []]
for node in nodes.values():
    group[node.rank % 2].append(node)
group.sort(key=len)
result = {}
x1 = set()
x2 = set()
x3 = set()

for i in range(1, N + 1):
    if i % 3 == 1:
        x1.add(i)
    elif i % 3 == 2:
        x2.add(i)
    else:
        x3.add(i)

for node in group[0]:
    if x1:
        result[node.v] = x1.pop()
    else:
        result[node.v] = x3.pop()

for node in group[1]:
    if x2:
        result[node.v] = x2.pop()
    else :
        result[node.v] = x3.pop()


print(' '.join(str(result[i]) for i in range(1, N + 1)))

Submission status: Runtime Error

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

def dfs(i,col):
    for k in x[i]:
        if c[k]==-1:
            c[k]=col
            if col==2:
                dfs(k,1)
            else:
                dfs(k,2)

dfs(0,c[0])
d=[]
e=[]
f=[]
for i in range(n):
    if c[i]==1:
        x=n//3+(0 if n%3==0 else 1)
        if len(d)==x:
            f.append(i+1)
        else:
            d.append(i+1)
    else:
        x=n//3+(1 if n%3==2 else 0)
        if len(e)==x:
            f.append(i+1)
        else:
            e.append(i+1)
ans=[-1]*n
g=[d,e,f]
g.sort(key=lambda x:len(x),reverse=True)
d,e,f=g
for i in range(n):
    if i%3==0:
        ans[i]=d[i//3]
    elif i%3==1:
        ans[i]=e[i//3]
    else:
        ans[i]=f[i//3]
print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
if N == 3:
    print(1, 2, 3)

x1 = set()
x2 = set()
x3 = set()

for i in range(1, N + 1):
    if i % 3 == 1:
        x1.add(i)
    elif i % 3 == 2:
        x2.add(i)
    else:
        x3.add(i)
x = [x1, x2, x3]

result = {}


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        if parent == None:
            result[self.v] = x1.pop()
        else:
            if x[(result[parent.v] + 1) % 3]:
                result[self.v] = x[(result[parent.v] + 1) % 3].pop()
            elif x1:
                result[self.v] =  x1.pop()
            elif x2:
                result[self.v] =  x2.pop()
            else:
                result[self.v] =  x3.pop()
        for node in self.linked:
            if node == parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

# usokaihou
root = nodes[1]
root.set_rank(None, 0)
print(' '.join(str(result[i]) for i in range(1, N + 1)))

exit()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)

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:
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() 
            elif set2:
                ans[i] = pop.set2()         
            elif 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() 
            elif set2:
                ans[i] = pop.set2()         
            elif 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:
                    print(-1)
                    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:
                    print(-1)
                    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:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(idx, pre_3, pre_2, pre_1):
    if pre_1 == -1:
        if pre_1 % 3 == 2 and len(edges[1]) > 0:
            out = edges[1].pop()
        elif pre_1 % 3 == 1 and len(edges[2]) > 0:
            out = edges[2].pop()
        else:
            out = edges[0].pop()
    else:
        if pre_1 % 3 != 0:
            if pre_1 % 3 == 2 and len(edges[1]) > 0:
                out = nums[1].pop()
            elif pre_1 % 3 == 1 and len(edges[2]) > 0:
                out = nums[2].pop()
            else:
                if len(edges[0]) > 0:
                    out = edges[0].pop()
                else:
                    print(-1)
                    exit()
        else:
            if len(edges[1]) > 0:
                out = nums[1].pop()
            elif len(edges[2]) > 0:
                out = nums[2].pop()
            else:
                if len(edges[0]) > 0:
                    out = edges[0].pop()
                else:
                    print(-1)
                    exit()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(step+1, k, pre_2, pre_1, out)

for i in range(1, n+1):
    if len(edges[i]) == 1:
        dfs(1, i, -1, -1, -1)
        break

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