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:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

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

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 0)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for i in range(1, 3):
                if len(nums[i]) > 0:
                    ans[i] = nums[i].pop()


if cnts[0] <= n // 3:
    solve(0)
elif cnts[1] <= n // 3:
    solve(1)
elif cnts[0] > n // 3 and cnts[1] > n // 3:
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()
else:
    print(-1)
    exit()

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for i in range(1, N + 1):
    if i % 3 == 0:
        mod0.append(i)
    elif i % 3 == 1:
        mod1.append(i)
    else:
        mod2.append(i)

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


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N // 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N // 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()
    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()


odd = 0
even = 0

bfs(0)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for i in range(N):
    modfit(i)
    print(node_p[i], end=" ")

print()

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

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

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 0)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for i in range(1, 3):
                if len(nums[i]) > 0:
                    ans[i] = nums[i].pop()


if cnts[0] <= n // 3:
    solve(0)
elif cnts[1] <= n // 3:
    solve(1)
else:
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
tree = [[0, 0] for _ in range(N+1)] # [parent, depth(e or o)]
edge = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

queue = deque([1])
d, even_or_odd = 1, [1, 0]
while len(queue) > 0:
    newq = set()
    for _ in range(len(queue)):
        p = queue.pop()
        for q in edge[p]:
            if q != tree[p][0]:
                newq.add(q)
                tree[q][0], tree[q][1] = p, d % 2
    even_or_odd[d % 2] += len(newq)
    d += 1
    queue = deque(list(newq))


if min(even_or_odd) >= N//3:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0 and i <= N//3:
            ans.append(3*i + 1)
            i += 1
        elif tree[l][1] != 0 and j <= N//3:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
elif even_or_odd[0] < N//3:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0:
            ans.append(3*k)
            k += 1
        elif i < N//3:
            ans.append(3*i + 1)
            i += 1
        elif j < N//3:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
else:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] != 0:
            ans.append(3*k)
            k += 1
        elif i < N//3:
            ans.append(3*i + 1)
            i += 1
        elif j < N//3:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
v=[-1]*n
v[0]=0
q=deque([0])
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
z=0
for i in v:
    if i==0:
        z+=1
ans=[0]*n
if z<=n//3:
    j=3
    for i in range(n):
        if v[i]==0:
            ans[i]=j
            j+=3
    j=1
    for i in range(n):
        if ans[i]==0:
            ans[i]=j
            j+=1
            if j%3==0 and j//3<=z:
                j+=1
    print(*ans)
elif n-z<=n//3:
    j=3
    for i in range(n):
        if v[i]==1:
            ans[i]=j
            j+=3
    j=1
    for i in range(n):
        if ans[i]==1:
            ans[i]=j
            j+=1
            if j%3==0 and j//3<=n-z:
                j+=1
    print(*ans)
else:
    o=1
    t=2
    tt=3
    for i in range(n):
        if v[i]==0 and o<=n:
            ans[i]=o
            o+=3
        elif v[i]==0:
            ans[i]=tt
            tt+=3
        if v[i]==1 and t<=n:
            ans[i]=t
            t+=3
        elif v[i]==1:
            ans[i]=tt
            tt+=3
    print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()
inf = 10**9
dist = [inf for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dist[i] = dist[node]+1
            dfs(i)
dist[1] = 0
rem_1 = [i+1 for i in range(n) if (i+1) % 3 == 1]
rem_2 = [i+1 for i in range(n) if (i+1) % 3 == 2]
rem_0 = [i+1 for i in range(n) if (i+1) % 3 == 0]
index_0 = 0
index_1 = 1
index_2 = 0
dfs(1)
ans = [1]
for i in range(2,len(dist)):
    if dist[i] % 2 == 1:
        if index_2 < len(rem_2):
            ans.append(rem_2[index_2])
            index_2 += 1
        else:
            if index_0 < len(rem_0):
                ans.append(rem_0[index_0])
                index_0 += 1
            else:
                print(-1)
                exit()
    else:
        if index_1 < len(rem_1):
            ans.append(rem_1[index_1])
            index_1 += 1
        else:
            if index_0 < len(rem_0):
                ans.append(rem_0[index_0])
                index_0 += 1
            else:
                print(-1)
                exit()
for i in ans:
    print(i, end=" ")

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)]
es = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

class TREE(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()
        # self.doubling()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]


depth = TREE(es).depth

ans = [0]*n

zero = one = two = n // 3
if n % 3 == 1: one += 1
if n % 3 == 2:
    one+=1
    two+=1


for i in range(n):
    if depth[i] % 2 == 0:
        if one > 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
else:
    print(*ans, sep=' ')
    exit()

zero = one = two = n // 3
if n % 3 == 1: one += 1
if n % 3 == 2:
    one+=1
    two+=1

for i in range(n):
    if depth[i] % 2 == 1:
        if one > 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
else:
    print(*ans, sep=' ')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d = [i % 2+1 for i in d]
    d2 = [0]*n
    x = d.count(1)
    y = d.count(2)
    if x >= n//3 and y >= n//3:
        j1 = 1
        for i in range(n):
            if d[i] == 1:
                d2[i] = j1
                j1 += 3
                cnt += 1
        j2 = 2
        for i in range(n):
            if d[i] == 2:
                d2[i] = j2
                j2 += 3
        j3 = 3
        for i in range(n):
            if d2[i] > n:
                d2[i] = j3
                j3 += 3
    elif x < n//3:
        j3 = 3
        for i in range(n):
            if d[i] == 1:
                d2[i] = j3
                j3 += 3
        j2 = 1
        for i in range(n):
            if d[i] == 2:
                d2[i] = j2
                if j2 % 3 == 2:
                    j2 += 2
                else:
                    j2 += 1
        for i in range(n):
            if d2[i] > n:
                d2[i] = j3
                j3 += 3
    else:
        j3 = 3
        for i in range(n):
            if d[i] == 2:
                d2[i] = j3
                j3 += 3
        j2 = 1
        for i in range(n):
            if d[i] == 1:
                d2[i] = j2
                if j2 % 3 == 2:
                    j2 += 2
                else:
                    j2 += 1
        for i in range(n):
            if d2[i] > n:
                d2[i] = j3
                j3 += 3
    print(*d2)


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d = [i % 2+1 for i in d]
    d2 = [0]*n
    x = d.count(1)
    y = d.count(2)
    if x >= n//3 and y >= n//3:
        j1 = 1
        for i in range(n):
            if d[i] == 1:
                d2[i] = j1
                j1 += 3
                cnt += 1
        j2 = 2
        for i in range(n):
            if d[i] == 2:
                d2[i] = j2
                j2 += 3
        j3 = 3
        for i in range(n):
            if d2[i] > n:
                d2[i] = j3
                j3 += 3
    elif x < n//3:
        j3 = 3
        for i in range(n):
            if d[i] == 1:
                d2[i] = j3
                j3 += 3
        j2 = 1
        for i in range(n):
            if d[i] == 2:
                d2[i] = j2
                if j2 % 3 == 2:
                    j2 += 2
                else:
                    j2 += 1
    else:
        j3 = 3
        for i in range(n):
            if d[i] == 2:
                d2[i] = j3
                j3 += 3
        j2 = 1
        for i in range(n):
            if d[i] == 1:
                d2[i] = j2
                if j2 % 3 == 2:
                    j2 += 2
                else:
                    j2 += 1
    print(*d2)


main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import deque

def main():
    n=int(input())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    Depth=[-1]*n
    Depth[0]=0
    q=deque()
    q.append(0)
    while q:
        fr=q.popleft()
        for to in Edges[fr]:
            if Depth[to]==-1:
                Depth[to]=Depth[fr]+1
                q.append(to)
    Group=[[] for _ in range(2)]
    for i in range(n):
        Group[Depth[i]%2].append(i)
    l_even,l_odd=len(Group[0]),len(Group[1])
    Ans=[0]*n
    Used=[False]*(n+1)
    if l_even<=l_odd:
        if l_even<n//3:
            tmp_3=3;tmp_others=1
            for i in Group[0]:
                Ans[i]=tmp_3
                Used[tmp_3]=True
                tmp_3+=3
            for i in Group[1]:
                while Used[tmp_others]:
                    tmp_others+=1
                Ans[i]=tmp_others
                Used[tmp_others]=True
            return Ans
    else:
        if l_odd<n//3:
            tmp_3=3;tmp_others=1
            for i in Group[1]:
                Ans[i]=tmp_3
                Used[tmp_3]=True
                tmp_3+=3
            for i in Group[0]:
                while Used[tmp_others]:
                    tmp_others+=1
                Ans[i]=tmp_others
                Used[tmp_others]=True
            return Ans
    tmp_even=1;tmp_odd=2;tmp_others=3
    for i in Group[0]:
        if tmp_even<=n:
            Ans[i]=tmp_even
            tmp_even+=3
        else:
            Ans[i]=tmp_others
            tmp_others+=3
    for i in Group[1]:
        if tmp_odd<=n:
            Ans[i]=tmp_odd
            tmp_odd+=3
        else:
            Ans[i]=tmp_others
            tmp_others+=3
    return Ans
    
if __name__=='__main__':
    Ans=main()
    print(*Ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
E = [[] for _ in range(N+1)]

if N == 2:
	print('1 2')
	sys.exit()

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

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

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

#mod0 = 6
#mod1 = 1
#mod2 = 2

#answer = [3]
#for i in range(2,N+1):
#	if dist[i] % 2 == 1:
#		if mod1 <= N:
#			answer.append(mod1)
#			mod1 += 3
#		else:
#			answer.append(mod0)
#			mod0 += 3
#	else:
#		if mod2 <= N:
#			answer.append(mod2)
#			mod2 += 3
#		else:
#			answer.append(mod0)
#			mod0 += 3

#print(*answer)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2

dfs(1)
bl = cl.count(1)
wh = N - bl

nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(nm)

res = [0] * (N + 1)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        f = 1
        break
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        f = 1
        break
if f:
  nm = [[] for _ in range(3)]
  for i in range(1, N + 1): nm[i % 3].append(i)
  res = [0] * (N + 1)
  for i in range(1, N + 1):
    if cl[i] == 0:
      if len(nm[1]):
        res[i] = nm[1].pop()
      else:
        if len(nm[0]):
          res[i] = nm[0].pop()
        else:
          print(-1)
          exit(0)
    else:
      if len(nm[2]):
        res[i] = nm[2].pop()
      else:
        if len(nm[0]):
          res[i] = nm[0].pop()
        else:
          print(-1)
          exit(0)
print(*res[1: ])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
N = int(input())
E = [[] for _ in range(N+1)]

if N == 2:
	print('1 2')
	sys.exit()

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

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

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

mod0 = 6
mod1 = 1
mod2 = 2

answer = [3]
for i in range(2,N+1):
	if dist[i] % 2 == 1:
		if mod1 <= N:
			answer.append(mod1)
			mod1 += 3
		else:
			answer.append(mod0)
			mod0 += 3
	else:
		if mod2 <= N:
			answer.append(mod2)
			mod2 += 3
		else:
			answer.append(mod0)
			mod0 += 3

print(*answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class Graph():
    def __init__(self,vertex_num,node_num,naive_input,start_zero=True,direction=False,weight=True):
        self.vertex_num=vertex_num
        self.node_num=node_num
        #nodeには入力時のインデックスも含む
        #[接続ノード , インッデクス]のarray
        node=[{} for _ in range(vertex_num)]
        for i in range(node_num):
            if weight:
                u,v,w=naive_input[i]
            else:
                u,v=naive_input[i]
                w=1
            if not start_zero:
                u-=1
                v-=1
            node[u][v]={"weight":w,"index":i}
            #node[v][u]={"weight":w,"index":i}
            if not direction:
                node[v][u]={"weight":w,"index":i}
                #node[u][v]["reverse"]={"weight":w,"index":i}
        self.node=node
        #それぞれの頂点の辺の数
        self.node_num_arr=list(map(lambda x:len(x),node))
        self.parent=[-1 for _ in range(self.vertex_num)]
        self.three=[set() for _ in range(self.vertex_num)]

    #頂点nowから順にbfs
    #頂点nowから順にbfs
    def bfs(self,s=0):
        def cal_distance(now_edge,next_edge,distance_arr):
            distance_arr[next_edge]=distance_arr[now_edge]+1

        def append_shinseki(now_edge,next_edge):
            p=self.parent[now_edge]
            p_child=set(self.node[p].keys())
            #print(self.parent)
            #print("parent:",p)
            #print("now;",now_edge,"next",next_edge)
            #print(p_child)
            p_child.remove(now_edge)
            self.three[next_edge]=p_child
        #bfs用のキュー
        q=[-1 for _ in range(self.vertex_num)]
        #pypyを使うときは要変更
        cal_node_num_arr=self.node_num_arr.copy()
        now_ind=0
        q[now_ind]=s
        last_ind=1


        distance=[0 for _ in range(self.vertex_num)]




        while last_ind<self.vertex_num:
            now_edge=q[now_ind]
            if cal_node_num_arr[now_edge]<=0:
                now_ind+=1
                continue
            for next_edge in self.node[now_edge]:
                #インデックスを利用したいときは要修正
                if cal_node_num_arr[next_edge]<=0:
                    continue
                cal_node_num_arr[now_edge]-=1
                cal_node_num_arr[next_edge]-=1
                q[last_ind]=next_edge
                self.parent[next_edge]=now_edge
                ##ここにやりたい処理をぶち込む！！
                #######cal_hogehoge()

                #頂点sから各頂点までの距離を計算する
                cal_distance(now_edge,next_edge,distance)
                if distance[next_edge]>1:
                    append_shinseki(now_edge,next_edge)
                last_ind+=1
            now_ind+=1
        return distance





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

g=Graph(n,n-1,n_i,start_zero=False,weight=False)
d_arr=g.bfs()
even=[]
odd=[]
for i in range(n):
    if d_arr[i]%2==0:
        even.append(i)
    else:
        odd.append(i)
ans=[-1 for _ in range(n)]
if min(len(even),len(odd))>n/3:
    num=1
    for i in even:
        ans[i]=num
        num+=3
        if num>n:
            break
    num=2
    for i in odd:
        ans[i]=num
        num+=3
        if num>n:
            break
    num=3
    for i in range(n):
        if ans[i]==-1:
            ans[i]=num
            num+=3
elif len(even)<=n/3:
    num=3
    for i in even:
        ans[i]=num
        num+=3
    last=len(odd)
    for j,i in enumerate(odd):
        ans[i]=num
        num+=3
        if num>n:
            last=j+1
            break
    num=1
    for i in odd[j+1:]:
        ans[i]=num
        if num%3==1:
            num+=1
        else:
            num+=2
else:
    num=3
    for i in odd:
        ans[i]=num
        num+=3
    last=len(even)
    for j,i in enumerate(even):
        ans[i]=num
        num+=3
        if num>n:
            last=j+1
            break
    num=1
    for i in even[j+1:]:
        ans[i]=num
        if num%3==1:
            num+=1
        else:
            num+=2

a=" ".join(map(str,ans))
print(a)

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)]
es = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

class TREE(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()
        # self.doubling()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]


depth = TREE(es).depth

ans = [0]*n


zero = one = two = n // 3
if n % 3 == 1: one += 1
if n % 3 == 2:
    one+=1
    two+=1


flg = 1

for i in range(n):
    if depth[i] % 2 == 0:
        if one > 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg = -1
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg = -1
            break

if flg == 1:
    print(*ans, sep=' ')
    exit()

flg2 = 1


zero = one = two = n // 3


for i in range(n):
    if depth[i] % 2 == 1:
        if one > 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg2 = -1
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg2 = -1
            break

if flg2 == 1:
    print(*ans, sep=' ')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

cl = [0] * (N + 1)
vis = set()
def dfs(x):
  global cl
  global vis
  vis.add(x)
  for y in e[x]:
    if y in vis: continue
    cl[y] = (cl[x] + 1) % 2

dfs(1)
bl = cl.count(1)
wh = N - bl

nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(nm)

res = [0] * (N + 1)
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        print(-1)
        exit(0)
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        print(-1)
        exit(0)

print(*res[1: ])

Submission status: Wrong Answer

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


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

Cl = [-1]*N
C = [[0], []]
q = [0]
c = 0
Cl[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np in graph[p]:
            if Cl[np]  == -1:
                Cl[np] = c
                C[c].append(np)
                qq.append(np)
    q = qq

# if len(C[0]) > len(C[1]):
#     C = [C[1], C[0]]

c0 = (N+2)//3
c1 = (N+1)//3
c2 = N//3
Co = [[], [], []]
if len(C[0]) < c1:
    R = set(C[0])
    for r in R:
        Co[2].append(r)
    for p in range(N):
        if p in R:
            continue
        elif len(Co[0]) < c0:
            Co[0].append(p)
        elif len(Co[1]) < c1:
            Co[1].append(p)
        else:
            Co[2].append(p)
elif len(C[1]) < c1:
    R = set(C[1])
    for r in R:
        Co[2].append(r)
    for p in range(N):
        if p in R:
            continue
        elif len(Co[0]) < c0:
            Co[0].append(p)
        elif len(Co[1]) < c1:
            Co[1].append(p)
        else:
            Co[2].append(p)
else:
    R2 = set(C[1])
    for p in range(N):
        if p in R2: # larger
            if len(Co[0]) < c0:
                Co[0].append(p)
            else:
                Co[2].append(p)
        else: # smaller
            if len(Co[1]) < c1:
                Co[1].append(p)
            else:
                Co[2].append(p)

ans = [None]*N
for i, n in enumerate(Co[0]):
    ans[n] = 3*i+1
for i, n in enumerate(Co[1]):
    ans[n] = 3*i+2
for i, n in enumerate(Co[2]):
    ans[n] = 3*i+3


print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
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)

inf=float("inf")

prv=[inf]*n
prv[0]=-1
depth=[inf]*n
depth[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next in edge[cur]:
    if prv[next]==inf:
      prv[next]=cur
      depth[next]=depth[cur]+1
      stack.append(next)
e,o=0,0
for i in range(n):
  if depth[i]%2:
    o+=1
  else:
    e+=1
Ans=[0]*n
if e<=n//3:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if not depth[i]%2:
      Ans[i]=3*ct3+3
      ct3+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      else:
        Ans[i]=3*ct1+1
        ct1+=1
elif o<=n//3:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if depth[i]%2:
      Ans[i]=3*ct3+3
      ct3+=1
    else:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      else:
        Ans[i]=3*ct2+2
        ct2+=1
else:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if not depth[i]%2:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1

print(*Ans)