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: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed == False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def bfs(pt,s):
    n = len(pt)
    d = [-1]*n
    d[s] = 0
    q = [s]
    c = 1
    while q:
        q1 = []
        for v in q:
            for u in pt[v]:
                if d[u] == -1:
                    d[u] = c
                    q1.append(u)
        q = q1
        c += 1
    return d

N = I()
a,b = LIR(N-1,2)

if N%3 == 0:
    one_num,two_num,zero_num = N//3,N//3,N//3
elif N%3 == 1:
    one_num,two_num,zero_num = N//3+1,N//3,N//3
else:
    one_num,two_num,zero_num = N//3+1,N//3+1,N//3

pt = edges_to_pt(a,b,N)
d = bfs(pt,0)

# 根からの距離の偶奇で群分け
odd = []
even = []
for i in range(N):
    if d[i]%2 == 0:
        even.append(i)
    else:
        odd.append(i)

max_ = max(len(even),len(odd))
min_ = min(len(even),len(odd))
if max_ == len(even):
    max_index = even
    min_index = odd
else:
    max_index = odd
    min_index = even

ans = [0]*N

# 各群の個数が十分多ければ，1と2を各群に振り分ける
if max_ >= one_num and min_ >= two_num:
    for i in range(one_num):
        ans[max_index[i]] = 1
    for i in range(two_num):
        ans[min_index[i]] = 2
# 片側の群の個数が少なければ，そちらに0を固める
else:
    for i in range(one_num):
        ans[max_index[i]] = 1
    for i in range(two_num):
        ans[max_index[i]] = 2

one_p = 0
two_p = 0
zero_p = 1
for i in range(N):
    if ans[i] == 1:
        ans[i] = 3*one_p+1
        one_p += 1
    elif ans[i] == 2:
        ans[i] = 3*two_p+2
        two_p += 1
    else:
        ans[i] = 3*zero_p
        zero_p += 1

print(*ans)

Submission status: Wrong Answer

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


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))


# あまり１、あまり２、あまり０になるように並び替え
X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]

# 少ない色の方は優先的に３の倍数を使うようにして塗る
ans = []
for color in colors:
    if X[color ^ 1]:
        ans.append(X[color ^ 1].pop())
    elif X[2]:
        ans.append(X[2].pop())
    else:
        ans.append(X[color].pop())

print(' '.join(map(str, ans)))

Submission status: Wrong Answer

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


colors = [-1] * N
stack = [(0, 0)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for to in T[n]:
        if colors[to] != -1:
            continue
        stack.append((to, color ^ 1))


# あまり１、あまり２、あまり０になるように並び替え
X = [[] for _ in range(3)]
for n in range(1, N + 1):
    X[n % 3].append(n)
X.append(X[0])
del X[0]


print(X)
print(colors)
# 少ない色の方は優先的に３の倍数を使うようにして塗る
ans = []
for color in colors:
    if X[color ^ 1]:
        ans.append(X[color ^ 1].pop())
    elif X[2]:
        ans.append(X[2].pop())
    else:
        ans.append(X[color].pop())

print(' '.join(map(str, ans)))

Submission status: Wrong Answer

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

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

# process
# 頂点を2グループに分類
group = [-1]*N
group[0] = False
def categorize2g(pi, i, g):
    for ci in Edges[i]:
        if ci == pi:
            continue
        group[ci] = not g
        categorize2g(i, ci, not g)

categorize2g(-1, 0, 0)

# 順列を求める
ans = [0]*N
mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]
gtnum = sum(group)
if gtnum < N//3:
    dq = deque(mod1+mod2+mod0)
elif gtnum < N*2//3:
    dq = deque(mod1+mod0+mod2)
else:
    dq = deque(mod0+mod1+mod2)

if len(ans) == N:
    for i, g in enumerate(group):
        if g:
            ans[i] = dq.pop()
        else:
            ans[i] = dq.popleft()

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

Submission status: Wrong Answer

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
def f(i):
    if tg[i] == 0 and mod3[1] <= N:
        ans[i] = mod3[1]
        mod3[1] += 3
    elif tg[i] == 1 and mod3[2] <= N:
        ans[i] = mod3[2]
        mod3[2] += 3
    elif mod3[0] <= N:
        ans[i] = mod3[0]
        mod3[0] += 3
    else:
        ans.clear
        return False
        
    g = (tg[i]+1)%2
    for p in Tree[i]:
        if p == i or tg[p] != -1:
            continue
        
        tg[p] = g
        if not f(p):
            return False
    
    return True

tg = [-1]*N
tg[0] = 0
ans = [0]*N
mod3 = [3, 1, 2]

f(0)

# output
# print(tg)

if len(ans) == 0:
    print(-1)
else:
    print(" ".join(map(str, ans)))

Submission status: Wrong Answer

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)

print(odd)
print(even)

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

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

else:
    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: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)
    
    red, black = list(), list()
    visited = [False] * N
    stack = [(0, True)]
    visited[0] = True
    while stack:
        v, is_red = stack.pop()
        if is_red: red.append(v)
        else: black.append(v)
        for to in G[v]:
            if visited[to]: continue
            visited[to] = True
            stack.append((to, not is_red))
    if len(red) < len(black): red, black = black, red

    ans = [0] * N
    if len(black) <= N//3:
        n = 3
        for v in black: ans[v], n = n, n + 3
        n = 1
        for v in red:
            ans[v], n = n, n + 1
            if n%3 == 0: n += 1
    else:
        n1, n2, n3 = 1, 2, 3
        for v in black:
            if n1 <= N: ans[v], n1 = n1, n1 + 3
            else: ans[v], n3 = n3, n3 + 3
        for v in red:
            if n2 <= N: ans[v], n2 = n2, n2 + 3
            else: ans[v], n3 = n3, n3 + 3
    print(*ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)

triger = 0

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

Submission status: Wrong Answer

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)

triger = 0

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

Submission status: Wrong Answer

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)

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

Submission status: Wrong Answer

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)

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

Submission status: Wrong Answer

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)

for i in range(1,n+1):
    if i%3 == 1 and len(odd):
        ans[odd.pop()] = i
    elif i%3 == 2 and len(even):
        ans[even.pop()] = i
    elif len(odd):
        ans[odd.pop()] = i
    elif len(even):
        ans[even.pop()] = i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1

"""

import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def Size(self,x):
        return self.size[self.find(x)]

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


n = onem()

tr = [[] for i in range(n)]
po = [0 for i in range(n)]

for i in range(n-1):
    a,b = m()
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)

de = cl.deque([[0,-1,0]])
bl = 0
re = 0
while de:
    data = de.popleft()
    if data[2] == 0:
        po[data[0]] = 1
        re += 1
    else:
        po[data[0]] = 2
        bl += 1
    for i in range(len(tr[data[0]])):
        if tr[data[0]][i] != data[1]:
            de.append([tr[data[0]][i],data[0],data[2]+1])

tr = n // 3

b0 = cl.deque([(i+1)*3 for i in range(tr)])
b1 = cl.deque([(i)*3+1 for i in range(tr+(1 if n % 3 >= 1 else 0))])
b2 = cl.deque([(i)*3+2 for i in range(tr+(1 if n % 3 >= 2 else 0))])

if re <= tr:
    for i in range(n):
        if po[i] == 1:
            po[i] = b0.popleft()
        else:
            if len(b1) != 0:
                po[i] = b1.popleft()
            elif len(b2) != 0:
                po[i] = b2.popleft()
            else:
                po[i] = b0.popleft()

elif bl <= tr:
    for i in range(n):
        if po[i] == 2:
            po[i] = b0.popleft()
        else:
            if len(b1) != 0:
                po[i] = b1.popleft()
            elif len(b2) != 0:
                po[i] = b2.popleft()
            else:
                po[i] = b0.popleft()


else:
    for i in range(n):
        if po[i] == 1:
            if len(b1) != 0:
                po[i] = b1.popleft()
            else:
                po[i] = b0.popleft()
        else:
            if len(b2) != 0:
                po[i] = b2.popleft()
            else:
                po[i] = b0.popleft()



print(jo(po))

Submission status: Wrong Answer

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np


from collections import deque
from collections import defaultdict


def main():
	N=int(input())
	M=N-1
	G = defaultdict(set)

	color = [0 for i in range(N + 1)]

	for _ in range(M):
		A, B = map(int, input().split())
		G[A].add(B)
		G[B].add(A)

	color[1] = 1
	que = deque([1])  # 始点を追加

	while len(que):
		p = que.popleft()  # 直近で追加したグラフの頂点を取得
		for q in list(G[p]):  # 結合しているグラフの頂点を参照
			if color[q] == 0:  # 塗られていないなら別の色で塗る
				color[q] = -color[p]
				que.append(q)


	b=[]
	w=[]
	for i in range(1,N+1):
		if color[i]==1:
			b.append(i)
		else:
			w.append(i)

	ans=[0]*(N+1)
	lim = ((N - 1) // 3)
	i=0
	if len(b)<len(w):
		for val in w:
			if i<=lim:
				ans[val]=3*i+1
				i+=1
			else:
				break
		w=w[i:]
	else:
		for val in b:
			if i<=lim:
				ans[val]=3*i+1
				i+=1
			else:
				break
		b=b[i:]


	lim = ((N - 2) // 3)
	i=0
	if len(b)<len(w):
		for val in w:
			if i<=lim:
				ans[val]=3*i+2
				i+=1
			else:
				break
		w=w[i:]
	else:
		for val in b:
			if i<=lim:
				ans[val]=3*i+2
				i+=1
			else:
				break
		b=b[i:]


	i=0
	for val in b:
		ans[val]=3*i+3
		i+=1
	for val in w:
		ans[val]=3*i+3




	print(*ans[1:])




if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

n = int(input())

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

used = [0]*n
tank = [0]
used[0] = 1
ca = 0
cb = 0
while tank:
    p = tank.pop()
    if used[p] > 0:
        ca += 1
    for e in edge[p]:
        if used[e] == 0:
            used[e] = -used[p]
            tank.append(e)
cb = n-ca
res = [0]*n
flag = [True]*(n+2)

if ca <= n//3:
    tmp = 0
    for i in range(n):
        if used[i] == 1:
            tmp += 3
            res[i] = tmp
            flag[tmp] = False
    tmp = 1
    for i in range(n):
        if used[i] != 1:
            res[i] = tmp
            while not flag[tmp]:
                tmp += 1
    print(*res)
elif cb <= n//3:
    tmp = 0
    for i in range(n):
        if used[i] == -1:
            tmp += 3
            res[i] = tmp
            flag[tmp] = False
    tmp = 1
    for i in range(n):
        if used[i] != -1:
            res[i] = tmp
            while not flag[tmp]:
                tmp += 1
    print(*res)
else:
    tmp = -2
    for i in range(n):
        if used[i] == -1:
            tmp += 3
            if tmp > n:
                tmp = 3
            res[i] = tmp
            flag[tmp] = False
    tmp = 2
    for i in range(n):
        if used[i] != -1:
            res[i] = tmp
            flag[tmp] = False
            while not flag[tmp]:
                tmp += 1
                if tmp > n:
                    tmp = 3
                    break
    print(*res)

Submission status: Wrong Answer

Solution code:
n=int(input())
c=[""]*(n+1)
p=[-1]*(n+1)
p[1]=0
st="1"
for i in range(n-1):
  a,b=map(int,input().split())
  c[min(a,b)]=c[min(a,b)]+str(max(a,b))
while len(st)>0:
  len_st=len(st)
  int_st=int(st[len_st-1])
  len_c=len(c[int_st])
  if len_c==0:
    st=st[:(len_st-1)]
    continue
  st=st+c[int_st]
  for s in list(c[int_st]):
    p[int(s)]=1-int(p[int_st])
  c[int_st]=""
p=p[1:len(p)]
sum_p=sum(p)
if(sum_p<n//3):
  a1=1
  a2=3
  a3=2
elif(n-sum_p<n//3):
  a1=3
  a2=1
  a3=2
else:
  a1=1
  a2=2
  a3=3
res=""
flg=0
for i in p:
  if i==0:
    if a1<=n:
      res=res+" "+str(a1)
      a1=a1+3
    else:
      if a3>n:
        flg=1
      res=res+" "+str(a3)
      a3=a3+3
  else:
    if a2<=n:
      res=res+" "+str(a2)
      a2=a2+3
    else:
      if a3>n:
        flg=1
      res=res+" "+str(a3)
      a3=a3+3
if flg==0:
  print(res)
else:
  print(-1)

Submission status: Wrong Answer

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,3):
        i = g1.pop()
        ans[i] = n
    for n in range(2,N+1,3):
        i = g2.pop()
        ans[i] = n
    for n in range(3,N+1,3):
        if n%3==1:
            i = g1.pop()
        elif n%3==2:
            i = g2.pop()
        ans[i] = n
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
lst = "3"
for i in range(N-1):
  a = input()
  lst += " 3"
print(lst)

Submission status: Wrong Answer

Solution code:
N = int(input())
lst = [3]
for i in range(N-1):
  a = input()
  lst.append(3)
print(lst)

Submission status: Wrong Answer

Solution code:
n=int(input())
c=[""]*(n+1)
p=[-1]*(n+1)
p[1]=0
st="1"
for i in range(n-1):
  a,b=map(int,input().split())
  c[min(a,b)]=c[min(a,b)]+str(max(a,b))
while len(st)>0:
  len_st=len(st)
  int_st=int(st[len_st-1])
  len_c=len(c[int_st])
  if len_c==0:
    st=st[:(len_st-1)]
    continue
  st=st+c[int_st]
  for s in list(c[int_st]):
    p[int(s)]=1-int(p[int_st])
  c[int_st]=""
p=p[1:len(p)]
if(sum(p)*2<n):
  a1=1
  a2=2
else:
  a1=2
  a2=1
a3=3
res=""
flg=0
for i in p:
  if i==0:
    if a1<=n:
      res=res+" "+str(a1)
      a1=a1+3
    else:
      if a3>n:
        flg=1
      res=res+" "+str(a3)
      a3=a3+3
  else:
    if a2<=n:
      res=res+" "+str(a2)
      a2=a2+3
    else:
      if a3>n:
        flg=1
      res=res+" "+str(a3)
      a3=a3+3
if flg==0:
  print(res)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
c=[""]*(n+1)
p=[-1]*(n+1)
p[1]=0
st="1"
for i in range(n-1):
  a,b=map(int,input().split())
  c[min(a,b)]=c[min(a,b)]+str(max(a,b))
while len(st)>0:
  len_st=len(st)
  int_st=int(st[len_st-1])
  len_c=len(c[int_st])
  if len_c==0:
    st=st[:(len_st-1)]
    continue
  st=st+c[int_st]
  for s in list(c[int_st]):
    p[int(s)]=1-int(p[int_st])
  c[int_st]=""
p=p[1:len(p)]
if(sum(p)*2<n):
  a1=1
  a2=2
else:
  a1=2
  a2=1
a3=3
res=""
flg=0
for i in p:
  if i==0:
    if a1<=n:
      res=res+str(a1)
      a1=a1+3
    else:
      if a3>n:
        flg=1
      res=res+str(a3)
      a3=a3+3
  else:
    if a2<=n:
      res=res+str(a2)
      a2=a2+3
    else:
      if a3>n:
        flg=1
      res=res+str(a3)
      a3=a3+3
if flg==0:
  print(res)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
c=[""]*(n+1)
p=[-1]*(n+1)
p[1]=0
st="1"
for i in range(n-1):
  a,b=map(int,input().split())
  c[min(a,b)]=c[min(a,b)]+str(max(a,b))
while len(st)>0:
  len_st=len(st)
  int_st=int(st[len_st-1])
  len_c=len(c[int_st])
  if len_c==0:
    st=st[:(len_st-1)]
    continue
  st=st+c[int_st]
  for s in list(c[int_st]):
    p[int(s)]=1-int(p[int_st])
  c[int_st]=""
p=p[1:len(p)]
if(sum(p)*2>n):
  a1=1
  a2=2
else:
  a1=2
  a2=1
a3=3
res=""
flg=0
for i in p:
  if i==0:
    if a1<=n:
      res=res+str(a1)
      a1=a1+3
    else:
      if a3>n:
        flg=1
      res=res+str(a3)
      a3=a3+3
  else:
    if a2<=n:
      res=res+str(a2)
      a2=a2+3
    else:
      if a3>n:
        flg=1
      res=res+str(a3)
      a3=a3+3
if flg==0:
  print(res)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    AB = [[] for j in range(N)]

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

    ans = [0] * N
    S = collections.deque()
    S.append([0, 0])
    v = set()
    v.add(0)
    while S:
        c = S.pop()
        ans[c[0]] = c[1] % 2
        for next in AB[c[0]]:
            if next not in v:
                v.add(next)
                S.append([next, c[1] + 1])

    q, r = divmod(N, 3)
    onenum = q
    twonum = q + N % 3
    if r == 1:
        onenum += 1
    elif r == 2:
        onenum += 1
        twonum += 1
    thrnum = q


    bnum = sum(ans)
    wnum = N - bnum

    onecnt = 0
    twocnt = 0
    thrcnt = 0

    if bnum <= thrnum:
        for a in ans:
            if a == 0:
                if twonum > 0:
                    twonum -= 1
                    print(twocnt * 3 + 2, end=" ")
                    twocnt += 1
                elif onenum > 0:
                    onenum -= 1
                    print(onecnt * 3 + 2, end=" ")
                    onecnt += 1
                else:
                    thrcnt += 1
                    print(thrcnt * 3, end=" ")
            else:
                thrcnt += 1
                print(thrcnt * 3, end=" ")
    elif wnum <= thrnum:
        for a in ans:
            if a == 1:
                if twonum > 0:
                    twonum -= 1
                    print(twocnt * 3 + 2, end=" ")
                    twocnt += 1
                elif onenum > 0:
                    onenum -= 1
                    print(onecnt * 3 + 2, end=" ")
                    onecnt += 1
                else:
                    thrcnt += 1
                    print(thrcnt * 3, end=" ")
            else:
                thrcnt += 1
                print(thrcnt * 3, end=" ")
    else:
        for a in ans:
            if bnum > N // 2:
                if a == 0:
                    if twonum > 0:
                        twonum -= 1
                        print(twocnt * 3 + 2, end=" ")
                        twocnt += 1
                    else:
                        thrcnt += 1
                        print(thrcnt * 3, end=" ")
                else:
                    if onenum > 0:
                        onenum -= 1
                        print(onecnt * 3 + 1, end=" ")
                        onecnt += 1
                    else:
                        thrcnt += 1
                        print(thrcnt * 3, end=" ")
            else:
                if a == 0:
                    if onenum > 0:
                        onenum -= 1
                        print(onecnt * 3 + 1, end=" ")
                        onecnt += 1
                    else:
                        thrcnt += 1
                        print(thrcnt * 3, end=" ")
                else:
                    if twonum > 0:
                        twonum -= 1
                        print(twocnt * 3 + 2, end=" ")
                        twocnt += 1
                    else:
                        thrcnt += 1
                        print(thrcnt * 3, end=" ")






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    AB = [[] for j in range(N)]

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

    ans = [0] * N
    S = collections.deque()
    S.append([0, 0])
    v = set()
    v.add(0)
    while S:
        c = S.pop()
        ans[c[0]] = c[1] % 2
        for next in AB[c[0]]:
            if next not in v:
                v.add(next)
                S.append([next, c[1] + 1])

    bcnt = sum(ans)
    q, r = divmod(N, 3)
    onenum = q
    twonum = q + N % 3
    if r == 1:
        onenum += 1
    elif r == 2:
        onenum += 1
        twonum += 1
    thrnum = q

    onecnt = 0
    twocnt = 0
    thrcnt = 0
    for a in ans:
        if bcnt > N // 2:
            if a == 0:
                if twonum > 0:
                    twonum -= 1
                    print(twocnt * 3 + 2, end=" ")
                    twocnt += 1
                else:
                    thrcnt += 1
                    print(thrcnt * 3, end=" ")
            else:
                if onenum > 0:
                    onenum -= 1
                    print(onecnt * 3 + 1, end=" ")
                    onecnt += 1
                else:
                    thrcnt += 1
                    print(thrcnt * 3, end=" ")
        else:
            if a == 0:
                if onenum > 0:
                    onenum -= 1
                    print(onecnt * 3 + 1, end=" ")
                    onecnt += 1
                else:
                    thrcnt += 1
                    print(thrcnt * 3, end=" ")
            else:
                if twonum > 0:
                    twonum -= 1
                    print(twocnt * 3 + 2, end=" ")
                    twocnt += 1
                else:
                    thrcnt += 1
                    print(thrcnt * 3, end=" ")






if __name__ == '__main__':
    main()