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
sys.setrecursionlimit(2*10**5)

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

# process
# treeを2グループに分類
def to2g(tg, i):
    g = (tg[i]+1)%2
    for p in Tree[i]:
        if tg[p] == 1:
            continue
        tg[p] = g
        to2g(tg, p)

tg = [-1]*(N)
tg[0] = 0
to2g(tg, 0)

# 順列を求める
ans = [0]*N
cnt0 = tg.count(0)
cnt1 = N-cnt0
if cnt0 < 2 or cnt1 < 2:
    for i in range(0, N):
        ans[i] = i+1
else:
    mod0 = 3
    mod1 = 1
    mod2 = 2
    for i, g in enumerate(tg):
        if g == 0 and mod1 <= N:
            ans[i] = mod1
            mod1 += 3
        elif g == 1 and mod2 <= N:
            ans[i] = mod2
            mod2 += 3
        elif mod0 <= N:
            ans[i] = mod0
            mod0 += 3
        else:
            ans = [-1]

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

Submission status: Runtime Error

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

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

# process
# treeを2グループに分類
def to2g(tg, i):
    g = (tg[i]+1)%2
    for p in Tree[i]:
        tg[p] = g
        to2g(tg, p)

tg = [-1]*(N)
tg[0] = 0
to2g(tg, 0)

# 順列を求める
ans = [0]*N
cnt0 = tg.count(0)
cnt1 = N-cnt0
if cnt0 < 2 or cnt1 < 2:
    for i in range(0, N):
        ans[i] = i+1
else:
    mod0 = 3
    mod1 = 1
    mod2 = 2
    for i, g in enumerate(tg):
        if g == 0 and mod1 <= N:
            ans[i] = mod1
            mod1 += 3
        elif g == 1 and mod2 <= N:
            ans[i] = mod2
            mod2 += 3
        elif mod0 <= N:
            ans[i] = mod0
            mod0 += 3
        else:
            ans = [-1]

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

Submission status: Runtime Error

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

# process
# treeを2グループに分類
tg = [-1]*(N)
tg[0] = 0
for i, t in enumerate(Tree):
    g = (tg[i]+1)%2
    for p in t:
        tg[p] = g

# 順列を求める
ans = [0]*N
cnt0 = tg.count(0)
cnt1 = N-cnt0
if cnt0 < 2 or cnt1 < 2:
    for i in range(0, N):
        ans[i] = i+1
else:
    mod0 = 3
    mod1 = 1
    mod2 = 2
    for i, g in enumerate(tg):
        if g == 0 and mod1 <= N:
            ans[i] = mod1
            mod1 += 3
        elif g == 1 and mod2 <= N:
            ans[i] = mod2
            mod2 += 3
        elif mod0 <= N:
            ans[i] = mod0
            mod0 += 3
        else:
            ans = [-1]

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

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

color = [-1] * n
def dfs(p, v, c):
    for nv in edge[v]:
        color[nv] = not c
        if nv == p:
            continue
        dfs(v, nv, not c)

dfs(-1, 0, 0)
white = sum(color)
black = n - white
if white > black:
    white, black = black, white
    color = [not item for item in color]

# Fill 0 mod 3 or not
if white <= n // 3:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    others = [item for item in range(1, n+1) if item % 3 != 0]
    array = deque(others + threes)
# Fill 1 mod 3 or 2 mod 3
else:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    twos = [item for item in range(1, n+1) if item % 3 == 2]
    ones = [item for item in range(1, n+1) if item % 3 == 1]
    array = deque(ones + threes + twos)

ans = [-1] * n
for i, is_white in enumerate(color):
    if is_white:
        ans[i] = array.pop()
    else:
        ans[i] = array.popleft()

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
 
sys.setrecursionlimit(10 ** 8)

n = int(input())

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

odd = []
even = []

ans = [-1] * n
def dfs(x, last = -1, d = 0):
    if d%2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:
            continue
        dfs(nxt, x, d + 1)

dfs(0)

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

for num in nums[1]:
    ans[odd.pop()] = num
for num in nums[2]:
    ans[even.pop()] = num
rest = nums[0] + nums[1] + nums[2]
for num in rest:
    if len(odd):
        ans[odd.pop()] = num
    elif len(even):
        ans[even.pop()] = num

print(*ans)

Submission status: Runtime Error

Solution code:
import sys
 
sys.setrecursionlimit(10 ** 6)

n = int(input())

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

odd = []
even = []

ans = [-1] * n
def dfs(x, last = -1, d = 0):
    if d%2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:
            continue
        dfs(nxt, x, d + 1)

dfs(0)

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

for num in nums[1]:
    ans[odd.pop()] = num
for num in nums[2]:
    ans[even.pop()] = num
rest = nums[0] + nums[1] + nums[2]
for num in rest:
    if len(odd):
        ans[odd.pop()] = num
    elif len(even):
        ans[even.pop()] = num

print(*ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X = [list(map(int, input().split())) for i in range(N-1)]
X = sorted(X, key = lambda x: (x[0], x[1]))

table = [[] for _ in range(N)]
for a, b in X:
    table[a-1].append(b)
odd = []
even = []
odd.append(1)

def classify_even_odd(x):
    for b in table[x-1]:
        if x == 1:
            odd.append(b)
        elif x in even and b not in odd:
            odd.append(b)
        elif x in odd and b not in even:
            even.append(b)
        classify_even_odd(b)
    return 0

def less_one_third(minority, majority):
    for index, x in enumerate(minority):
        value = 3*index +3
        ans[x-1] = value
        p.remove(value)
    for index, x in enumerate(majority):
        ans[x-1] = p[index]
    return ans

def greater_one_third():
    for i in range(N//3 +1):
        even_value = 3*i +2
        ans[even.pop(0) -1] = even_value
        p.remove(even_value)

        odd_value = 3*i +1
        ans[odd.pop(0) -1] = odd_value
        p.remove(odd_value)

    for x in even:
        ans[x-1] = p.pop(0)
    for x in odd:
        ans[x-1] = p.pop(0)
    return ans

for i in range(1, N+1):
    classify_even_odd(i)
p = [i+1 for i in range(N)]
ans = [0 for i in range(N)]

if len(odd) <= N/3:
    ans = less_one_third(odd, even)
elif len(even) <= N/3:
    ans = less_one_third(even, odd)
else:
    ans = greater_one_third()
for output in ans:
    print(output, end=' ')

Submission status: Runtime Error

Solution code:
N = int(input())
X = [list(map(int, input().split())) for i in range(N-1)]
X = sorted(X, key = lambda x: (x[0], x[1]))

table = [[] for _ in range(N)]
for a, b in X:
    table[a-1].append(b)
odd = []
even = []
odd.append(1)

def classify_even_odd(x):
    for b in table[x-1]:
        if x == 1:
            odd.append(b)
        elif x in even and b not in odd:
            odd.append(b)
        elif x in odd and b not in even:
            even.append(b)
        classify_even_odd(b)
    return 0

def less_one_third(minority, majority):
    for index, x in enumerate(minority):
        value = 3*index +3
        ans[x-1] = value
        p.remove(value)
    for index, x in enumerate(majority):
        ans[x-1] = p[index]
    return ans

def greater_one_third():
    even_size, odd_size = len(even), len(odd)
    for i in range(N//3 +1):
        if i < even_size:
            even_value = 3*i +1
            ans[even[0]-1] = even_value
            p.remove(even_value)
            even.remove(even[0])
        if i < odd_size:
            odd_value = 3*i +2
            ans[odd[0]-1] = odd_value
            p.remove(odd_value)
            odd.remove(odd[0])

    for index, x in enumerate(even):
        ans[x-1] = p[0]
        p.remove(p[0])
    for index, x in enumerate(odd):
        ans[x-1] = p[0]
        p.remove(p[0])
    # ans[0] = p[0]
    return ans

for i in range(1, N+1):
    classify_even_odd(i)
p = [i+1 for i in range(N)]
ans = [0 for i in range(N)]

if len(odd) <= N/3:
    ans = less_one_third(odd, even)
elif len(even) <= N/3:
    ans = less_one_third(even, odd)
else:
    ans = greater_one_third()
for output in ans:
    print(output, end=' ')

Submission status: Runtime Error

Solution code:
N = int(input())
X = [list(map(int, input().split())) for i in range(N-1)]
X = sorted(X, key = lambda x: (x[0], x[1]))

table = [[] for _ in range(N)]
for a, b in X:
    table[a-1].append(b)
odd = []
even = []
odd.append(1)

def add(x):
    for b in table[x-1]:
        if x == 1:
            odd.append(b)
        elif x in even and b not in odd:
            odd.append(b)
        elif x in odd and b not in even:
            even.append(b)
        add(b)
    return 0

def less_one_third(minority, majority):
    for index, x in enumerate(minority):
        value = 3*index +3
        ans[x-1] = value
        p.remove(value)
    for index, x in enumerate(majority):
        ans[x-1] = p[index]
        p.remove(p[index])
    # ans[0] = p[0]
    return ans

def greater_one_third():
    even_size, odd_size = len(even), len(odd)
    for i in range(N//3 +1):
        if i < even_size:
            even_value = 3*i +1
            ans[even[0]-1] = even_value
            p.remove(even_value)
            even.remove(even[0])
        if i < odd_size:
            odd_value = 3*i +2
            ans[odd[0]-1] = odd_value
            p.remove(odd_value)
            odd.remove(odd[0])

    for index, x in enumerate(even):
        ans[x-1] = p[index]
        p.remove(p[index])
    for index, x in enumerate(odd):
        ans[x-1] = p[index]
        p.remove(p[index])
    # ans[0] = p[0]
    return ans

for i in range(1, N+1):
    add(i)
p = [i+1 for i in range(N)]
ans = [0 for i in range(N)]

if len(odd) <= N/3:
    ans = less_one_third(odd, even)
elif len(even) <= N/3:
    ans = less_one_third(even, odd)
else:
    ans = greater_one_third()
for output in ans:
    print(output, end=' ')

Submission status: Runtime Error

Solution code:
N = int(input())
X = [list(map(int, input().split())) for i in range(N-1)]
X = sorted(X, key = lambda x: (x[0], x[1]))

table = [[] for _ in range(N)]
for a, b in X:
    table[a-1].append(b)
odd = []
even = []
odd.append(1)

def add(x):
    for b in table[x-1]:
        if x == 1:
            odd.append(b)
            add(b)
        elif x in even and b not in odd:
            odd.append(b)
            add(b)
        elif x in odd and b not in even:
            even.append(b)
            add(b)
    return 0

def less_one_third(minority, majority):
    for index, x in enumerate(minority):
        value = 3*index +3
        ans[x-1] = value
        p.remove(value)
    for index, x in enumerate(majority):
        ans[x-1] = p[index]
        p.remove(p[index])
    # ans[0] = p[0]
    return ans

def greater_one_third():
    even_size, odd_size = len(even), len(odd)
    for i in range(N//3 +1):
        if i < even_size:
            even_value = 3*i +1
            ans[even[0]-1] = even_value
            p.remove(even_value)
            even.remove(even[0])
        if i < odd_size:
            odd_value = 3*i +2
            ans[odd[0]-1] = odd_value
            p.remove(odd_value)
            odd.remove(odd[0])

    for index, x in enumerate(even):
        ans[x-1] = p[index]
        p.remove(p[index])
    for index, x in enumerate(odd):
        ans[x-1] = p[index]
        p.remove(p[index])
    # ans[0] = p[0]
    return ans

for i in range(1, N+1):
    add(i)
p = [i+1 for i in range(N)]
ans = [0 for i in range(N)]

if len(odd) <= N/3:
    ans = less_one_third(odd, even)
elif len(even) <= N/3:
    ans = less_one_third(even, odd)
else:
    ans = greater_one_third()
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

def load(vtype=int):
    return vtype(input().strip())

def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]

def exit():
    import sys
    sys.exit(0)

RED = True
BLACK = False
class Node():
    def __init__(self, n):
        self.n = n
        self.adjs = []
        self.color = None
        self.p = None

    def __str__(self):
        return str(self.n)+ " " + ",".join([str(a.n) for a in self.adjs]) + " color: %s" % self.color
    
N = load()

nodes = [Node(i) for i in range(0, N+1)]

for _ in range(N-1):
    a, b = load_list()
    nodes[a].adjs.append(nodes[b])

color_list = defaultdict(list)
def paint(node, color):
    color_list[color].append(node)
    node.color = color
    if node.adjs:
        for a in node.adjs:
            paint(a, not color)

paint(nodes[1], RED)

# print(len(color_list[RED]))
# print(len(color_list[BLACK]))

amari = defaultdict(list)
for i in range(1, N+1):
    amari[i % 3].append(i)
    
if len(color_list[RED]) <= int(N/3):
    for red in color_list[RED]:
        red.p = amari[0].pop()
    for black in color_list[BLACK]:
        if len(amari[0]):
            black.p = amari[0].pop()
        elif len(amari[1]):
            black.p = amari[1].pop()
        else:
            black.p = amari[2].pop()

elif len(color_list[BLACK]) <= int(N/3):
    for black in color_list[BLACK]:
        black.p = amari[0].pop()
    for red in color_list[RED]:
        if len(amari[0]):
            red.p = amari[0].pop()
        elif len(amari[1]):
            red.p = amari[1].pop()
        else:
            red.p = amari[2].pop()   
else:
    for black in color_list[BLACK]:
        if len(amari[1]):
            black.p = amari[1].pop()
    for red in color_list[RED]:
        if len(amari[2]):
            red.p = amari[2].pop()


results = []
for n in nodes[1:]:
    if n.p is None:
        results.append(amari[0].pop())
    else:
        results.append(n.p)
print(" ".join([str(r) for r in results]))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

def load(vtype=int):
    return vtype(input().strip())

def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]

def exit():
    import sys
    sys.exit(0)

RED = True
BLACK = False
class Node():
    def __init__(self, n):
        self.n = n
        self.adjs = []
        self.color = None
        self.p = None

    def __str__(self):
        return str(self.n)+ " " + ",".join([str(a.n) for a in self.adjs]) + " color: %s" % self.color
    
N = load()

nodes = [Node(i) for i in range(0, N+1)]

for _ in range(N-1):
    a, b = load_list()
    nodes[a].adjs.append(nodes[b])

color_list = defaultdict(list)
def paint(node, color):
    color_list[color].append(node)
    node.color = color
    if node.adjs:
        for a in node.adjs:
            paint(a, not color)

paint(nodes[1], RED)

# print(len(color_list[RED]))
# print(len(color_list[BLACK]))

amari = defaultdict(list)
for i in range(1, N+1):
    amari[i % 3].append(i)
    
if len(color_list[RED]) <= int(N/3):
    for red in color_list[RED]:
        red.p = amari[0].pop()
    for black in color_list[BLACK]:
        if len(amari[0]):
            black.p = amari[0].pop()
        elif len(amari[1]):
            black.p = amari[1].pop()
        else:
            black.p = amari[2].pop()

elif len(color_list[BLACK]) <= int(N/3):
    for black in color_list[BLACK]:
        black.p = amari[0].pop()
    for red in color_list[RED]:
        if len(amari[0]):
            black.p = amari[0].pop()
        elif len(amari[1]):
            black.p = amari[1].pop()
        else:
            black.p = amari[2].pop()   
else:
    for black in color_list[BLACK]:
        if len(amari[1]):
            black.p = amari[1].pop()
    for red in color_list[RED]:
        if len(amari[2]):
            red.p = amari[2].pop()


results = []
for n in nodes[1:]:
    if n.p is None:
        results.append(amari[0].pop())
    else:
        results.append(n.p)
print(" ".join([str(r) for r in results]))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

vector <int> from[100010];
int ans[100010];
int cnt[10];

void dfs(int x, int last) {
	cnt[ans[x]]++;
	for (int i = 0; i < from[x].size(); i++) {
		int v = from[x][i];
		if (v == last) continue;
		ans[v] = 3 - ans[x], dfs(v, x);
	}
}

int main () {
	int n; scanf("%d", &n);
	int a = n / 3, b = (n + 2) / 3, c = (n + 1) / 3;
	for (int i = 1; i < n; i++) {
		int x, y; scanf("%d%d", &x, &y);
		from[x].push_back(y);
		from[y].push_back(x);
	}
	ans[1] = 1, dfs(1, 1);
	if (cnt[1] < cnt[2]) {
		for (int i = 1; i <= n; i++) {
			ans[i] = 3 - ans[i];
		}
		swap(cnt[1], cnt[2]);
	}
	if (cnt[1] <= b + a) {
		int t1 = cnt[1] - b, t2 = cnt[2] - c;
		for (int i = 1; i <= n; i++) {
			if (ans[i] == 1) {
				if (t1) t1--, ans[i] = 0;
			} else {
				if (t2) t2--, ans[i] = 0;
			}
		}
		int now[3] = {3, 1, 2};
		for (int i = 1; i <= n; i++) {
			printf("%d ", now[ans[i]]);
			now[ans[i]] += 3;
		}
		printf("\n");
		return 0;
	}
	int T = c;
	for (int i = 1; i <= n; i++) {
		if (ans[i] == 2) {
			ans[i] = 0;
		} else if (ans[i] == 1) {
			if (T--) ans[i] = 2;
		}
	}
	int now[3] = {3, 1, 2};
	for (int i = 1; i <= n; i++) {
		printf("%d ", now[ans[i]]);
		now[ans[i]] += 3;
	}
	printf("\n");
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)


ans = [-1]*(n+1)
q = [1]
ans[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if ans[next] == -1:
            q.append(next)
            ans[next] = (ans[now]+1)%2

if ans.count(1) <= n//3:
    three = set([3*i+3 for i in range(n//3)])
    onetwo = set([i+1 for i in range(n)])
    onetwo = onetwo - three
    three = list(three)
    three.sort()
    onetwo = list(onetwo)
    onetwo.sort()
    three_ind = 0
    onetwo_ind = 0
    for i in range(1, n+1):
        if ans[i] == 1:
            ans[i] = three[three_ind]
            three_ind += 1
        else:
            ans[i] = onetwo[onetwo_ind]
            onetwo_ind += 1

elif ans.count(0) <= n//3:
    three = set([3*i+3 for i in range(n//3)])
    onetwo = set([i+1 for i in range(n)])
    onetwo = onetwo - three
    three = list(three)
    three.sort()
    onetwo = list(onetwo)
    onetwo.sort()
    three_ind = 0
    onetwo_ind = 0
    for i in range(1, n+1):
        if ans[i] == 0:
            ans[i] = three[three_ind]
            three_ind += 1
        else:
            ans[i] = onetwo[onetwo_ind]
            onetwo_ind += 1

else:
    zero = 0
    one = 0
    two = 0
    for i in range(1, n+1):
        if ans[i] == 0:
            ans[i] = zero*3+1
            zero += 1
        elif ans[i] == 1:
            ans[i] = one*3+2
            one += 1

    three = 0
    for i in range(1, n+1):
        if ans[i] > n:
            ans[i] = three*3+3
            three += 1

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

g1 = []
g2 = []
for i,d in enumerate(depth):
    if d%2:
        g2.append(i)
    else:
        g1.append(i)
if len(g1) < len(g2):
    g1,g2 = g2,g1

ans = [None] * N
if len(g2) <= N//3:
    for n in range(1,N+1):
        if n%3==0:
            if g2:
                i = g2.pop()
            else:
                i = g1.pop()
        else:
            i = g1.pop()
        ans[i] = n
else:
    for n in range(1,N+1):
        if n%3==1:
            i = g1.pop()
        elif n%3==2:
            i = g2.pop()
        else:
            if (n//3)%2:
                i = g1.pop()
            else:
                i = g2.pop()
        ans[i] = n
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

g1 = []
g2 = []
for i,d in enumerate(depth):
    if d%2:
        g2.append(i)
    else:
        g1.append(i)
if len(g1) < len(g2):
    g1,g2 = g2,g1

ans = [None] * N
if len(g2) <= N//3:
    for n in range(1,N+1):
        if n%3==0:
            if g2:
                i = g2.pop()
            else:
                i = g1.pop()
        else:
            i = g1.pop()
        ans[i] = n
else:
    for n in range(1,N+1):
        if n%3==1:
            i = g1.pop()
        elif n%3==2:
            i = g2.pop()
        else:
            if g1:
                i = g1.pop()
            else:
                i = g2.pop()
        ans[i] = n
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

g1 = []
g2 = []
for i,d in enumerate(depth):
    if d%2:
        g2.append(i)
    else:
        g1.append(i)
if len(g1) < len(g2):
    g1,g2 = g2,g1

ans = [None] * N
if len(g2) <= N//3:
    for n in range(1,N+1):
        if n%3==0 and g2:
            i = g2.pop()
        else:
            if g1:
                i = g1.pop()
            else:
                i = g2.pop()
        ans[i] = n
else:
    for n in range(1,N+1):
        if n%3==1:
            i = g1.pop()
        elif n%3==2:
            i = g2.pop()
        else:
            if g1:
                i = g1.pop()
            else:
                i = g2.pop()
        ans[i] = n
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

g1 = []
g2 = []
for i,d in enumerate(depth):
    if d%2:
        g2.append(i)
    else:
        g1.append(i)
if len(g1) < len(g2):
    g1,g2 = g2,g1

ans = [None] * N
if len(g2) <= N//3:
    for n in range(1,N+1):
        if n%3==0 and g2:
            i = g2.pop()
        else:
            i = g1.pop()
        ans[i] = n
else:
    for n in range(1,N+1):
        if n%3==1:
            i = g1.pop()
        elif n%3==2:
            i = g2.pop()
        else:
            if g1:
                i = g1.pop()
            else:
                i = g2.pop()
        ans[i] = n
print(*ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
const int inf=1000000007;
const int MOD=1000000007;
struct Tree{
  int p;
  int num;
  int par;
  bool tag;
  bool comp;
  vector<int> edge;
  int count(){
    num=edge.size();
    return num;
  }
};
signed main(){
  int n;cin>>n;
  vector<Tree> tree(n+1);
  rep(i,n-1){
    int a,b;cin>>a>>b;
    tree[a].edge.push_back(b);
    tree[b].edge.push_back(a);
  }
  rep(i,n+1){
    tree[i].tag=true;
    tree[i].comp=true;
    //cout<<i<<endl;
  }
  //return 0;
  //tree[0].comp=true;
  queue<int> que;que.push(1);
  tree[1].comp=false;
  while(!que.empty()){
    int buf=que.front();que.pop();
    int num=tree[buf].count();
    rep(i,num){
      if(tree[tree[buf].edge[i]].comp){
        tree[tree[buf].edge[i]].comp=false;
        que.push(tree[buf].edge[i]);
        tree[tree[buf].edge[i]].tag=!tree[buf].tag;
      }
    }
  }
  int T=0;int F=0;
  rep1(i,n){
    if(tree[i].tag)T++;
    else F++;
  }
  int one=0;int two=0;int three=0;
  if(T<=n/3){
    rep1(i,n){
      if(tree[i].tag){
        three++;
        cout<<three*3;
      }
      else{
        one++;
        if(one%3==0)one++;
        cout<<one;
      }
      cout<<" ";
    }
  }
  else if(F<=n/3){
    rep1(i,n){
      if(!tree[i].tag){
        three++;
        cout<<three*3;
        tree[1000000].p=1;
      }
      else{
        one++;
        if(one%3==0)one++;
        cout<<one;
      }
      cout<<" ";
    }
  }
  else{
    rep1(i,n){
      if(tree[i].tag){
        if(one*3+1<=n){
          cout<<one*3+1;
          one++;
        }
        else{
          three++;
          cout<<three*3;
        }
      }
      else{
        if(two*3+2<=n){
          cout<<two*3+2;
          two++;
        }
        else{
          three++;
          cout<<three*3;
        }
      }
      cout<<" ";
    }
  }
  cout<<endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
N = int(input())
E = [[] for _ in range(N+1)]

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

grp = [[] for _ in range(2)]

def dfs(cu, pa=-1, col=0):
    grp[col].append(cu)
    for to in E[cu]:
        if to != pa:
            dfs(to, cu, 1 - col)

dfs(0)

A = len(grp[0])
B = len(grp[1])

one = N // 3; one += (1 if 1 <= N % 3 else 0) # 2
two = N // 3; two += (1 if 2 <= N % 3 else 0) # 2
thr = N // 3;                                 # 1

if A > B:
    A, B = B, A
    grp[0], grp[1] = grp[1], grp[0]

ans = [[] for _ in range(N)]

if two <= A:
    # grp[0]を全部2にして、残りは3
    x = 2
    for i in range(two):
        ans[grp[0][i]] = x; x += 3;
    x = 1
    for i in range(one):
        ans[grp[1][i]] = x; x += 3;
    x = 3
    for i in range(two, A):
        ans[grp[1][i]] = x; x += 3;
    for i in range(one, B):
        ans[grp[1][i]] = x; x += 3;
else:
    # grp[0]を全部3にする
    x = 3
    for i in range(A):
        ans[grp[0][i]] = x; x += 3; thr -= 1;
    for i in range(thr):
        ans[grp[1][i]] = x; x += 3;
    x = 1
    for i in range(one):
        ans[grp[1][thr+i]] = x; x += 3;
    x = 2
    for i in range(two):
        ans[grp[1][thr+one+i]] = x; x += 3;

print(*ans, sep=" ")

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

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

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

p = [0]*n

depth = [-1]*n
depth[0] = 0

q = [0]

cnt = [1, 0]

while q:
    v = q.pop()
    for w in g[v]:
        if depth[w] != -1:
            continue
        depth[w] = depth[v] + 1
        cnt[depth[w] % 2] += 1
        q.append(w)


ans = [0]*n

if cnt[0] <= n//3:
    ans[0] = lst[0].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 == 0:
                ans[w] = lst[0].pop()
            else:
                if lst[1]:
                    ans[w] = lst[1].pop()
                else:
                    ans[w] = lst[2].pop()
            q.append(w)
elif cnt[1] <= n//3:
    ans[0] = lst[1].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 != 0:
                ans[w] = lst[0].pop()
            else:
                if lst[1]:
                    ans[w] = lst[1].pop()
                else:
                    ans[w] = lst[2].pop()
            q.append(w)
else:
    ans[0] = lst[2].pop()
    q = [0]
    while q:
        v = q.pop()
        for w in g[v]:
            if ans[w] != 0:
                continue
            if depth[w] % 2 != 0:
                if lst[1]:
                    ans[w] = lst[1].pop()
                else:
                    ans[w] = lst[0].pop()
            else:
                if lst[2]:
                    ans[w] = lst[2].pop()
                else:
                    ans[w] = lst[0].pop()
            q.append(w)

print(*ans)