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, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def bfs(n,g):
    dis = [-1 for _ in range(n)]
    que = deque([])
    que.append(0)
    dis[0] = 0
    ODD = []
    EVEN = [0]
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] != -1:
                continue
            dis[g[go][i]] = dis[go] + 1
            if dis[g[go][i]]%2 == 0:
                EVEN.append(g[go][i])
            else:
                ODD.append(g[go][i])
            que.append(g[go][i])
    return EVEN,ODD

def main():
    n = inp()
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = inpm()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    EVEN,ODD = bfs(n,g)
    ans = [0 for _ in range(n)]
    check = [1 for _ in range(n)]
    if len(ODD) <= n//3:
        x = 1
        while ODD:
            index = ODD.pop()
            ans[index] = 3*x
            check[3*x-1] = 0
            x += 1
        i = 0
        while EVEN:
            index = EVEN.pop()
            while not check[i]:
                i += 1
            ans[index] = check[i]
            i += 1
        print(*ans)
        return
    if len(EVEN) <= n//3:
        x = 1
        while EVEN:
            index = EVEN.pop()
            ans[index] = 3*x
            check[3*x-1] = 0
            x += 1
        i = 0
        while ODD:
            index = ODD.pop()
            while not check[i]:
                i += 1
            ans[index] = check[i]
            i += 1
        print(*ans)
        return
    mod0 = deque()
    mod1 = deque()
    mod2 = deque()
    for i in range(1,n+1):
        if i%3 == 0:
            mod0.append(i)
        if i%3 == 1:
            mod1.append(i)
        if i%3 == 2:
            mod2.append(i)
    while mod1:
        index = EVEN.pop()
        ans[index] = mod1.pop()
    while mod2:
        index = ODD.pop()
        ans[index] = mod2.pop()
    while mod0:
        if EVEN:
            index = EVEN.pop()
        else:
            index = ODD.pop()
        ans[index] = mod0.pop()
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

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

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

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

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

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

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

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

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n = int(input())
G = [[] for i in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b-=1
  G[a].append(b)
  G[b].append(a)
ans = [0] * n
color = [[],[]]
def coloring(node,pre,oddeven):
  color[oddeven%2].append(node)
  for vi in G[node]:
    if vi != pre:
      coloring(vi,node,oddeven+1)
  return

coloring(0,-1,0)
A = n//3 + int(bool(n%3))
B = n//3 + int(n%3 == 2)
C = n//3
# この時点ではA>=Bである
if len(color[0]) < len(color[1]):
  A,B = B,A
a=b=0; c=1
if len(color[0]) > C and len(color[1]) > C:
  for i,ci in enumerate(color[0]):
    if i < A:
      ans[ci] = 3 * i + 1
    else:
      ans[ci] = 3 * c
      c += 1

  for i,ci in enumerate(color[1]):
    if i < B:
      ans[ci] = 3 * i + 2
    else:
      ans[ci] = 3 * c
      c += 1

elif len(color[0]) <= C:
  # elseが読まれるとき必ずlen(color[0]) < A
  # Bは条件を満たすはず
  for i ,ci in enumerate(color[0]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[1]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

else:
  # elseが読まれるとき必ずlen(color[0]) < A
  # そんなことなかったwwww
  for i ,ci in enumerate(color[1]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[0]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

color=[-1 for i in range(n)]
color[0]=0
def coloring(x):
    for i in G[x]:
        if color[i] != -1:continue
        color[i]=1-color[x]
        coloring(i)
coloring(0)
A=[];B=[]
ans=[0 for i in range(n)]
for i in range(n):
    if color[i]==0:A.append(i)
    else:B.append(i)


if 1:
    if len(A)>len(B):
        A,B=B,A
    
    qq=deque([i for i in range(3,n+1,3)]+[i for i in range(1,n+1,3)]+[i for i in range(2,n+1,3)])
    for i in A:
        ans[i]=qq.popleft()
    for i in B:
        ans[i]=qq.popleft()
            
    print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n = int(input())
G = [[] for i in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b-=1
  G[a].append(b)
  G[b].append(a)
ans = [0] * n
color = [[],[]]
def coloring(node,pre,oddeven):
  color[oddeven%2].append(node)
  for vi in G[node]:
    if vi != pre:
      coloring(vi,node,oddeven+1)
  return

coloring(0,-1,0)
A = n//3 + int(bool(n%3))
B = n//3 + int(n%3 == 2)
C = n//3
# この時点ではA>=Bである
if len(color[0]) < len(color[1]):
  A,B = B,A
a=b=0; c=1
if len(color[0]) > C and len(color[1]) > C:
  for i,ci in enumerate(color[0]):
    if i < A:
      ans[ci] = 3 * i + 1
    else:
      ans[ci] = 3 * c
      c += 1

  for i,ci in enumerate(color[1]):
    if i < B:
      ans[ci] = 3 * i + 2
    else:
      ans[ci] = 3 * c
      c += 1

elif len(color[0]) <= C:
  # elseが読まれるとき必ずlen(color[0]) < A
  # Bは条件を満たすはず
  for i ,ci in enumerate(color[0]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[1]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1
elif len(color[0]) <= C:
  # elseが読まれるとき必ずlen(color[0]) < A
  # Bは条件を満たすはず
  for i ,ci in enumerate(color[0]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[1]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

else:
  # elseが読まれるとき必ずlen(color[0]) < A
  # そんなことなかったwwww
  for i ,ci in enumerate(color[1]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[0]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

print(*ans)

Submission status: Wrong Answer

Solution code:
n,*L=map(int,open(0).read().split())
g=[[]for _ in range(n)]
for a,b in zip(*[iter(L)]*2):
	g[a-1].append(b-1)
	g[b-1].append(a-1)
tr=[-1]*n
q=[0]
tr[0]=0
while q:
	cu=q.pop()
	for nx in g[cu]:
		if tr[nx]<0:
			tr[nx]=1-tr[cu]
			q.append(nx)
lab=[-1]*n
z,o=map(tr.count,(0,1))
if z<=n//3 or o<=n//3:
	f=0 if z<=n//3 else 1
	onetwo=1
	thr=3
	for i,x in enumerate(tr):
		if x==f:
			lab[i]=thr
			thr+=3
		else:
			lab[i]=onetwo
			onetwo+=1
			if onetwo%3==0:
				onetwo+=1
else:
	one=1
	for i,x in enumerate(tr):
		if x==0:
			lab[i]=one
			one+=3
			if one>n:
				break
	two=2
	for i,x in enumerate(tr):
		if x==1:
			lab[i]=two
			two+=3
			if two>n:
				break
	thr=3
	for i in range(n):
		if lab[i]<0:
			lab[i]=thr
			thr+=3
print(*lab)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n = int(input())
G = [[] for i in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b-=1
  G[a].append(b)
  G[b].append(a)
ans = [0] * n
color = [[],[]]
def coloring(node,pre,oddeven):
  color[oddeven%2].append(node)
  for vi in G[node]:
    if vi != pre:
      coloring(vi,node,oddeven+1)
  return

coloring(0,-1,0)
A = n//3 + int(bool(n%3))
B = n//3 + int(n%3 == 2)
# この時点ではA>=Bである
if len(color[0]) < len(color[1]):
  A,B = B,A
a=b=0; c=1
if len(color[0]) >= A and len(color[1]) >= B:
  for i,ci in enumerate(color[0]):
    if i < A:
      ans[ci] = 3 * i + 1
    else:
      ans[ci] = 3 * c
      c += 1

  for i,ci in enumerate(color[1]):
    if i < B:
      ans[ci] = 3 * i + 2
    else:
      ans[ci] = 3 * c
      c += 1

elif len(color[0]) < A:
  # elseが読まれるとき必ずlen(color[0]) < A
  # Bは条件を満たすはず
  for i ,ci in enumerate(color[0]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[1]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1
elif len(color[0]) < A:
  # elseが読まれるとき必ずlen(color[0]) < A
  # Bは条件を満たすはず
  for i ,ci in enumerate(color[0]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[1]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

else:
  # elseが読まれるとき必ずlen(color[0]) < A
  # そんなことなかったwwww
  for i ,ci in enumerate(color[1]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[0]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n = int(input())
G = [[] for i in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b-=1
  G[a].append(b)
  G[b].append(a)
ans = [0] * n
color = [[],[]]
def coloring(node,pre,oddeven):
  color[oddeven%2].append(node)
  for vi in G[node]:
    if vi != pre:
      coloring(vi,node,oddeven+1)
  return

coloring(0,-1,0)
A = n//3 + int(bool(n%3))
B = n//3 + int(n%3 == 2)
# この時点ではA>=Bである
if len(color[0]) < len(color[1]):
  A,B = B,A
a=b=0; c=1
if len(color[0]) >= A and len(color[1]) >= B:
  for i,ci in enumerate(color[0]):
    if i < A:
      ans[ci] = 3 * i + 1
    else:
      ans[ci] = 3 * c
      c += 1

  for i,ci in enumerate(color[1]):
    if i < B:
      ans[ci] = 3 * i + 2
    else:
      ans[ci] = 3 * c
      c += 1

else:
  # elseが読まれるとき必ずlen(color[0]) < A
  # Bは条件を満たすはず
  for i ,ci in enumerate(color[0]):
    ans[ci] = 3 * c
    c += 1
  for i ,ci in enumerate(color[1]):
    if a < A:
      ans[ci] = 3 * a + 1
      a += 1
    elif b < B:
      ans[ci] = 3 * b + 2
      b += 1
    else:
      ans[ci] = 3 * c
      c += 1

print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n = int(input())
G = [[] for i in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b-=1
  G[a].append(b)
  G[b].append(a)
ans = [0] * n
color = [[],[]]
def coloring(node,pre,oddeven):
  color[oddeven%2].append(node)
  for vi in G[node]:
    if vi != pre:
      coloring(vi,node,oddeven+1)
  return

coloring(0,-1,0)
A = n//3 + int(bool(n%3))
B = n//3 + int(n%3 == 2)
# この時点ではA>=Bである
if color[0] < color[1]:
  A,B = B,A
a=b=0; c=1
for i,ci in enumerate(color[0]):
  if i < A:
    ans[ci] = 3 * i + 1
  else:
    ans[ci] = 3 * c
    c += 1

for i,ci in enumerate(color[1]):
  if i < B:
    ans[ci] = 3 * i + 2
  else:
    ans[ci] = 3 * c
    c += 1
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(b)
  
colors = [-1] * n

# ２色で塗分けする。
q = deque()
# 現在見ている頂点、親の色
q.append((0, 0))
while q:
  v, pcol = q.popleft()
  # 親と異なる色で塗る。
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
    for i in e[v]:
      if colors[i] == -1:
        q.append((i, col))

m = [deque([i for i in range(1, n + 1) if i % 3 == j]) for j in range(3)]

# print(m)

def opop(n):
  if m[n]:
    p = m[n].pop()
  else:
    if n == 1 or n == 2:
      if m[0]:
        p = m[0].pop()
      else:
        p = m[3-n].pop()
    else:
      if m[1]:
        p = m[1].pop()
      else:
        p = m[2].pop()
  return p

ans = [0] * n

if sum(colors) <= n // 3:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(0)
    else:
      ans[itr] = opop(1)
elif sum(colors) >= n - (n // 3) + 1:
  for itr, i in enumerate(colors):
    if not i:
      ans[itr] = opop(0)
    else:
      ans[itr] = opop(1)
else:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(1)
    else:
      ans[itr] = opop(2)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(b)
  
colors = [-1] * n

# ２色で塗分けする。
q = deque()
# 現在見ている頂点、親の色
q.append((0, 0))
while q:
  v, pcol = q.popleft()
  # 親と異なる色で塗る。
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
    for i in e[v]:
      if colors[i] == -1:
        q.append((i, col))

m = [deque([i for i in range(1, n + 1) if i % 3 == j]) for j in range(3)]

# print(m)

def opop(n):
  if m[n]:
    p = m[n].pop()
  else:
    if n == 1 or n == 2:
      if m[0]:
        p = m[0].pop()
      else:
        p = m[3-n].pop()
    else:
      if m[1]:
        p = m[1].pop()
      else:
        p = m[2].pop()
  return p

ans = [0] * n

if sum(colors) < n // 3:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(0)
    else:
      ans[itr] = opop(1)
elif sum(colors) > n - (n // 3) + 1:
  for itr, i in enumerate(colors):
    if not i:
      ans[itr] = opop(0)
    else:
      ans[itr] = opop(1)
else:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(1)
    else:
      ans[itr] = opop(2)
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(b)
  
colors = [-1] * n

# ２色で塗分けする。
q = deque()
# 現在見ている頂点、親の色
q.append((0, 0))
while q:
  v, pcol = q.popleft()
  # 親と異なる色で塗る。
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
    for i in e[v]:
      if colors[i] == -1:
        q.append((i, col))

m = [deque([i for i in range(1, n + 1) if i % 3 == j]) for j in range(3)]

# print(m)

def opop(n):
  if m[n]:
    p = m[n].pop()
  else:
    if n == 1 or n == 2:
      if m[0]:
        p = m[0].pop()
      else:
        p = m[3-n].pop()
    else:
      if m[1]:
        p = m[1].pop()
      else:
        p = m[2].pop()
  return p

ans = [0] * n

if sum(colors) < n // 3:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(0)
    else:
      ans[itr] = opop(1)
elif sum(colors) > n - (n // 3) + 1:
  for itr, i in enumerate(colors):
    if not i:
      ans[itr] = opop(0)
    else:
      ans[itr] = opop(1)
else:
  for itr, i in enumerate(colors):
    print(itr)
    if i:
      ans[itr] = opop(1)
    else:
      ans[itr] = opop(2)
print(*ans)

Submission status: Wrong Answer

Solution code:
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)

color=[-1]*N
color[0]=0
next_i=[0]
visited=[0]*N
while next_i:
    i=next_i.pop()
    visited[i]=1
    while tree[i]:
        x=tree[i].pop()
        if visited[x]==0:
            next_i.append(x)
            color[x]=color[i]^1
if 0 in visited:
    for i in range(N):
        if visited[i]==0:
            next_i.append(i)
while next_i:
    i=next_i.pop()
    visited[i]=1
    while tree[i]:
        x=tree[i].pop()
        if visited[x]==0:
            next_i.append(x)
            color[x]=color[i]^1

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
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)

color=[-1]*N
color[0]=0
next_i=[0]
visited=[0]*N
while next_i:
    i=next_i.pop()
    visited[i]=1
    while tree[i]:
        x=tree[i].pop()
        if visited[x]==0:
            next_i.append(x)
            color[x]=color[i]^1


n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
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)

color=[-1]*N
color[0]=0
next_i=[0]
while next_i:
    i=next_i.pop()
    while tree[i]:
        x=tree[i].pop()
        if color[x]==-1:
            next_i.append(x)
            color[x]=color[i]^1

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
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)

color=[-1]*N
color[0]=0
next_i=[0]
while next_i:
    i=next_i.pop()
    while tree[i]:
        x=tree[i].pop()
        if color[x]==-1:
            next_i.append(x)
            color[x]=color[i]

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
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)

color=[-1]*N
def coloring(n):
    if n==0:
        color[0]=0
    if color[n]==-1:
        coloring(n-1)
    while tree[n]:
        a=tree[n].pop()
        color[a]=color[n]^1
try:
    coloring(N-1)
except:
    print('-1')
    exit()

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)