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 collections import defaultdict

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]

d = defaultdict(list)
class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self,rank,parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor == parent:
                continue
            neighbor.set_rank(rank=rank+1,parent=self)



trees = {i:Tree(i) for i in range(1,N+1)}

for a,b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
trees[1].set_rank(1,None)

group0 = [node.v for node in  trees.values() if node.rank %2 ==0]
group1 = [node.v for node in  trees.values() if node.rank %2]
x = [set(),set(),set()]
for i in range(1,N+1):
    x[i%3].add(i)
if len(group1) < len(group0):
    group1,group0 = group0,group1

result = {}
if len(group0) <= len(x[0]):
    while group0:
        result[group0.pop()]= x[0].pop()
    y = x[0]|x[1]|x[2]
    while group1:
        result[group1.pop()] = y.pop()
else:
    while x[1] and group0:
        result[group0.pop()] = x[1].pop()
    while x[2] and group1:
        result[group1.pop()] = x[2].pop()
    while group0:
        result[group0.pop()] = x[0].pop()
    while group1:
        result[group1.pop()] = x[0].pop()

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]

d = defaultdict(list)
class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self,rank,parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor == parent:
                continue
            neighbor.set_rank(rank=rank+1,parent=self)



trees = {i:Tree(i) for i in range(1,N+1)}

for a,b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
trees[1].set_rank(1,None)

group0 = [node.v for node in  trees.values() if node.rank %2 ==0]
group1 = [node.v for node in  trees.values() if node.rank %2]
x = [set(),set(),set()]
for i in range(1,N+1):
    x[i%3].add(i)
if len(group1) < len(group0):
    group1,group0 = group0,group1

result = {}
if len(group0) <= N//3:
    while group0:
        result[group0.pop()]= x[0].pop()
    y = x[0]|x[1]|x[2]
    while group1:
        result[group1.pop()] = y.pop()
else:
    while x[1] and group0:
        result[group0.pop()] = x[1].pop()
    while x[2] and group1:
        result[group1.pop()] = x[2].pop()
    while group0:
        result[group0.pop()] = x[0].pop()
    while group1:
        result[group1.pop()] = x[0].pop()

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

Submission status: Runtime Error

Solution code:
import heapq


n = int(input())
tree = [[] for i in range(n+1)]
dep_table = [[] for i in range(n+1)]
dep_table[0].append(1)
depth = 1 
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    
    if not a in dep_table[depth-1]:
        depth += 1
    dep_table[depth].append(b)

order = [[] for i in range(n+1)]
depth_num = 0
for i in range(len(dep_table)):
    for j in dep_table[i]:
        if depth_num == depth:
            break

        if depth_num==depth-2 and depth_num==depth-1:
            not_under = list(set(dep_table[depth_num+1])-set(tree[j]))
            order[j] = not_under
        else:
            not_under = list(set(dep_table[depth_num+1])-set(tree[j]))
            order[j] = dep_table[depth_num+3]+not_under
    else:
        depth_num += 1

mult3 = n//3
if n%3 == 2:
    plus1 = n//3+1
    plus2 = n//3+1
else:
    plus1 = n//3+1
    plus2 = n//3

ord_len = []
ans_list = [0 for i in range(n+1)]


def insert_2():
    global ans_list, plus1, plus2
    poped = heapq.heappop(ord_len)
    ans_list[poped[1]] = 2
    plus2 -= 1
    for i in range(poped[0]):
        comb = order[poped[1]][i]
        if ans_list[comb] == 0:
            if plus1 == 0:
                return -1
            ans_list[comb] = 1
            plus1 -= 1
        elif ans_list[comb] == 1:
            pass
        else:
            return -1

def insert_1():
    global ans_list, plus1, plus2
    poped = heapq.heappop(ord_len)
    ans_list[poped[1]] = 1
    plus1 -= 1
    for i in range(poped[0]):
        comb = order[poped[1]][i]
        if ans_list[comb] == 0:
            if plus2 == 0:
                return -1
            ans_list[comb] = 2
            plus2 -= 1
        elif ans_list[comb] == 2:
            pass
        else:
            return -1

for i in range(len(order)):
    heapq.heappush(ord_len, [-1*len(order[i]), i])
while mult3 != 0 and ord_len[0] != 0:
    ans_list[heapq.heappop(ord_len)[1]] = 3
    mult3 -= 1
else:
    if ord_len[0] == 0:
        pass
    else:
        while ord_len[0][0] != 0:
            if plus1 == 0:
                if insert_2() == -1:
                    print(-1)
                    break
            elif plus2 == 0:
                if insert_1() == -1:
                    print(-1)
                    break
            elif plus1 > plus2:
                if insert_2() == -1:
                    print(-1)
                    break
            else:
                if insert_1() == -1:
                    print(-1)
                    break
        else:                           # 条件の対象のみ順列が完成 
            for i in range(1, n+1):
                if ans_list[i] == 0:
                    if mult3 != 0:
                        ans_list[i] = 3
                        mult3 -= 1
                    elif plus1 != 0:
                        ans_list[i] = 1
                        plus1 -= 1
                    elif plus2 != 0:
                        ans_list[i] = 2
                        plus2 -= 1

            count1 = 0
            count2 = 0
            count3 = 0
            for i in range(1, n+1):
                if ans_list[i] == 1:
                    ans_list[i] = 3*count1+1
                    count1 += 1
                elif ans_list[i] == 2:
                    ans_list[i] = 3*count2+2
                    count2 += 1
                elif ans_list[i] == 3:
                    ans_list[i] = 3*count3+3
                    count3 += 1
            for i in range(1, n+1):
                if i==n:
                    print(ans_list[i])
                else:
                    print(ans_list[i], end="")

Submission status: Runtime Error

Solution code:
from collections import deque

import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

dist = [10**10] * N
que = deque([(0, 0)])
while que:
    now, d = que.popleft()

    if dist[now] <= d:
        continue
    dist[now] = d

    for to in edges[now]:
        que.append((to, d + 1))

A = [i for i, d in enumerate(dist) if d % 2 == 0]
B = [i for i, d in enumerate(dist) if d % 2 == 1]

if len(A) > len(B):
    A, B = B, A

ans = [-1] * N

if len(A) <= N // 3:
    nums = set(range(1, N + 1))
    now = 3
    for i in A:
        ans[i] = now
        nums.remove(now)
        now += 3
    nums = list(nums)
    for i, n in zip(B):
        ans[i] = n
else:
    now = 0
    nums = set(range(1, N + 1))
    for i in A:
        if now + 1 > N:
            break
        ans[i] = now + 1
        nums.remove(now + 1)
        now += 3
    now = 0
    for i in B:
        if now + 2 > N:
            break
        ans[i] = now + 2
        nums.remove(now + 2)
        now += 3
    now = 3
    for i, a in enumerate(ans):
        if a == -1:
            ans[i] = now
            now += 3

print(*ans)

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)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[0] > num[1]:
   odd, even = even, odd
if num[0] > n / 3 and num[0] > n / 3:
    r = r2 + r0 + r1
else:
    r = r2 + r1 + r0
ans = [0] * n
for i in even:
    ans[i] = r.pop()
for i in odd:
    ans[i] = r.pop()
print(f'{odd=}{even=}{num=}')
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if even < odd:
    even, odd = odd, even
if len(odd) >= (n + 2) // 3:
    print(1)
    for i in range(1, n + 1):
        if i % 3 == 2:
            ans[even.pop()] = i
        elif i % 3 == 1:
            ans[odd.pop()] = i
    for j in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = j
        else:
            ans[even.pop()] = j
else:
    for i in range(1, n + 1):
        if odd and i % 3 == 0:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if even < odd:
    even, odd = odd, even
if len(odd) >= (n + 2) // 3:
    for i in range(1, n + 1):
        if i % 3 == 2:
            ans[even.pop()] = i
        elif i % 3 == 1:
            ans[odd.pop()] = i
    for j in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = j
        else:
            ans[even.pop()] = j
else:
    for i in range(1, n + 1):
        if odd and i % 3 == 0:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i
            print(10)

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if even < odd:
    even, odd = odd, even
if len(odd) >= (n + 2) // 3:
    for i in range(1, n + 1):
        if i % 3 == 2:
            ans[even.pop()] = i
        elif i % 3 == 1:
            ans[odd.pop()] = i
    for j in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = j
        else:
            ans[even.pop()] = j
else:
    for i in range(1, n + 1):
        if odd and i % 3 == 0:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if even < odd:
    even, odd = odd, even
if len(odd) >= n // 3 + bool(n % 3):
    for i in range(1, n + 1):
        if i % 3 == 2:
            ans[even.pop()] = i
        elif i % 3 == 1:
            ans[odd.pop()] = i
    for j in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = j
        else:
            ans[even.pop()] = j
else:
    for i in range(1, n + 1):
        if odd and i % 3 == 0:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if even < odd:
    even, odd = odd, even
if len(odd) >= n // 2 + bool(n % 3):
    for i in range(1, n + 1):
        if i % 3 == 2:
            ans[even.pop()] = i
        elif i % 3 == 1:
            ans[odd.pop()] = i
    for j in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = j
        else:
            ans[even.pop()] = j
else:
    for i in range(1, n + 1):
        if odd and i % 3 == 0:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if len(even) >= n // 3 + bool(n % 3 >= 2) and len(odd) >= n // 3 + bool(n % 3 >= 1):
    for i in range(1, n + 1):
        if i % 3 == 2:
            ans[even.pop()] = i
        elif i % 3 == 1:
            ans[odd.pop()] = i
    for j in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = j
        else:
            ans[even.pop()] = j
else:
    if even < odd:
        even, odd = odd, even
    for i in range(1, n + 1):
        if odd and i % 3 == 0:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if len(even) >= n // 3 and len(odd) >= n // 3:
    for i in range(1, n + 1, 3):
        ans[even.pop()] = i
    for j in range(2, n + 1, 3):
        ans[odd.pop()] = j
    for k in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = k
        else:
            ans[even.pop()] = k
else:
    if even < odd:
        even, odd = odd, even
    for i in range(n + 1):
        if odd and i % 3 == 0:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if len(even) >= n // 3 + bool(n % 3 >= 2) and len(odd) >= n // 3 + bool(n % 3 >= 1):
    for i in range(1, n + 1):
        if i % 3 == 2:
            ans[even.pop()] = i
        elif i % 3 == 1:
            ans[odd.pop()] = i
    for j in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = j
        else:
            ans[even.pop()] = j

else:
    if even < odd:
        even, odd = odd, even
    for i in range(n + 1):
        if odd and i % 3 == 0:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i

print(*ans)

Submission status: Runtime Error

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

n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n-1)]

edges = {}
for i in range(1,n+1):
    edges[i] = set()

for tmp in ab:
    a,b = tmp
    edges[a].add(b)
    edges[b].add(a)

group = [[],[]]
g_flag = 0
next = {1}
while(len(next) > 0):
    tmp = list(next)
    next = set()
    for i in tmp:
        group[g_flag].append(i)
        for j in edges[i]:
            next.add(j)
            edges[j].remove(i)
    g_flag = 1- g_flag

even_n = len(group[0])
odd_n = len(group[1])

ans = [0] * (n+1)
if(even_n > n//3)&(odd_n > n//3):
    g1 = group[0][ : (n+2)//3]
    g2 = group[1][ : (n+1)//3]
    g0 = group[0][(n+2)//3 :] + group[1][(n+1)//3 :]
elif(even_n <= n//3):
    g0 = group[0].extend(group[1][: n//3 - even_n])
    g1 = group[1][n//3 - even_n : (n//3 - even_n) + (n+2)//3]
    g2 = group[1][(n//3 - even_n) + (n+2)//3 :]
else:
    g0 = group[1].extend(group[0][: n//3 - odd_n])
    g1 = group[1][n//3 - odd_n : (n//3 - odd_n) + (n+2)//3]
    g2 = group[1][(n//3 - odd_n) + (n+2)//3 :]

# print(group)
# print(g0)
# print(g1)
# print(g2)

for i in range((n+2)//3):
    ans[g1[i]] = i*3 + 1
for i in range((n+1)//3):
    ans[g2[i]] = i*3 + 2
for i,val in enumerate(g0):
    ans[val] = (i+1) * 3

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

Submission status: Runtime Error

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

n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n-1)]

edges = {}
for i in range(1,n+1):
    edges[i] = set()

for tmp in ab:
    a,b = tmp
    edges[a].add(b)
    edges[b].add(a)

group = [[],[]]
g_flag = 0
next = {1}
while(len(next) > 0):
    tmp = list(next)
    next = set()
    for i in tmp:
        group[g_flag].append(i)
        for j in edges[i]:
            next.add(j)
            edges[j].remove(i)
    g_flag = 1- g_flag

even_n = len(group[0])
odd_n = len(group[1])

ans = [0] * (n+1)
if(even_n > n//3)&(odd_n > n//3):
    g1 = group[0][ : (n+2)//3]
    g2 = group[1][ : (n+1)//3]
    g0 = group[0][(n+2)//3 :] + group[1][(n+1)//3 :]
elif(even_n <= n//3):
    g0 = group[0].extend(group[1][: n//3 - even_n])
    g1 = group[1][n//3 - even_n : (n//3 - even_n) + (n+2)//3]
    g2 = group[1][(n//3 - even_n) + (n+2)//3 :]
else:
    g0 = group[1].extend(group[0][: n//3 - odd_n])
    g1 = group[1][n//3 - odd_n : (n//3 - odd_n) + (n+2)//3]
    g2 = group[1][(n//3 - odd_n) + (n+2)//3 :]

print(group)
print(g0)
print(g1)
print(g2)

for i in range((n+2)//3):
    ans[g1[i]] = i*3 + 1
for i in range((n+1)//3):
    ans[g2[i]] = i*3 + 2
for i,val in enumerate(g0):
    ans[val] = (i+1) * 3

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


col = [0] * n
dq = deque([0])
col[0] = 1
visited = [0] * n
visited[0] = 1
even = {0}
odd = set()
while dq:
    u = dq.pop()
    for v in G[u]:
        if visited[v]:
            continue
        visited[v] = 1
        col[v] = -col[u]
        if col[v] == 1:
            even.add(v)
        else:
            odd.add(v)
        dq += [v]


ans = [0] * n
if len(even) >= n // 3 and len(odd) >= n // 3:
    for i in range(1, n + 1, 3):
        ans[even.pop()] = i
    for j in range(2, n + 1, 3):
        ans[odd.pop()] = j
    for k in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = k
        else:
            ans[even.pop()] = k
else:
    if even < odd:
        even, odd = odd, even
    for i in range(3, n + 1, 3):
        if odd:
            ans[odd.pop()] = i
        else:
            ans[even.pop()] = i
    for j in range(1, n + 1):
        if j % 3 == 0:
            continue
        ans[even.pop()] = j


print(*ans)