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: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

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

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

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

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

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

print(*ans)

Submission status: Accepted

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
		i+=1




	print(*ans[1:])




if __name__ == "__main__":
	main()

Submission status: Accepted

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

n = int(input())

g = [[] for _ in range(n)]

ans = [-1] * n
odd = []
even = []
nums = [[], [], []]
for i in range(1, n + 1):
    nums[i % 3].append(i)

def dfs(v, p = -1, d = 0):
    if d % 2:
        odd.append(v)
    else:
        even.append(v)

    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, d + 1)

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

dfs(0)

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 odd_node in odd:
        if len(nums[1]) != 0:
            ans[odd_node] = nums[1].pop()
        else:
            ans[odd_node] = nums[0].pop()
    for even_node in even:
        if len(nums[2]) != 0:
            ans[even_node] = nums[2].pop()
        else:
            ans[even_node] = nums[0].pop()

print(*ans)

Submission status: Accepted

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
            flag[tmp] = False
            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
            flag[tmp] = False
            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: Accepted

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


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

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

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

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

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

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

Submission status: Accepted

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 g1:
            i = g1.pop()
        else:
            i = g2.pop()
        ans[i] = n
print(*ans)

Submission status: Accepted

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である
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

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: Accepted

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: Accepted

Solution code:
from collections import deque


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    group = [set() for _ in range(2)]
    q = deque([(0, 0, -1)])
    while len(q):
        cur, g, prev = q.popleft()
        group[g].add(cur)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, 1-g, cur))
    if len(group[0]) > len(group[1]):
        tmp = group[0]
        group[0] = group[1]
        group[1] = tmp
    ans = [0] * N
    pool = set(range(1, N+1))
    if len(group[0]) <= N//3:
        for i, x in enumerate(group[0]):
            ans[x] = (i+1)*3
            pool.remove((i+1)*3)
        for x in group[1]:
            ans[x] = pool.pop()
    else:
        cand = (list(range(1, N+1, 3)) +
                list(range(3, N+1, 3)))[:len(group[0])]
        for x, v in zip(group[0], cand):
            ans[x] = v
            pool.remove(v)
        for x in group[1]:
            ans[x] = pool.pop()
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():

    N = int(input())
    g = {}
    for i in range(N):
        g[i] = set()

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

    # BFS
    dist = [-1] * N     # [-1:initial, 0:even, 1:odd]
    dist[0] = 0
    n_even = 0
    que = deque([0])
    while len(que):
        v = que[0]
        if dist[v] % 2 == 0:
            n_even += 1
        que.popleft()
        for n in g[v]:
            if dist[n] == -1:
                dist[n] = (dist[v] + 1) % 2
                que.append(n)

    ans = [-1] * N
    if n_even <= int(N / 3):
        n3, n3q, n3r = 1, 0, 1
        for i in range(N):
            if dist[i] == 0:
                ans[i] = n3 * 3
                n3 += 1
            else:
                if n3q * 3 + n3r <= N:
                    ans[i] = n3q * 3 + n3r
                    if n3r == 1:
                        n3r = 2
                    else:
                        n3q += 1
                        n3r = 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
    elif n_even > int(N * 2 / 3):
        n3, n3q, n3r = 1, 0, 1
        for i in range(N):
            if dist[i] == 1:
                ans[i] = n3 * 3
                n3 += 1
            else:
                if n3q * 3 + n3r <= N:
                    ans[i] = n3q * 3 + n3r
                    if n3r == 1:
                        n3r = 2
                    else:
                        n3q += 1
                        n3r = 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
    else:
        n3, n31, n32 = 1, 0, 0
        for i in range(N):
            if dist[i] == 0:
                if n31 * 3 + 1 <= N:
                    ans[i] = n31 * 3 + 1
                    n31 += 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
            else:
                if n32 * 3 + 2 <= N:
                    ans[i] = n32 * 3 + 2
                    n32 += 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():

    N = int(input())
    g = {}
    for i in range(N):
        g[i] = set()

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

    # BFS
    dist = [-1] * N     # [-1:initial, 0:even, 1:odd]
    dist[0] = 0
    n_even = 0
    que = deque([0])
    while len(que):
        v = que[0]
        if dist[v] % 2 == 0:
            n_even += 1
        que.popleft()
        for n in g[v]:
            if dist[n] == -1:
                dist[n] = (dist[v] + 1) % 2
                que.append(n)

    ans = [-1] * N
    if n_even <= int(N / 3):
        n3, n3q, n3r = 1, 0, 1
        for i in range(N):
            if dist[i] == 0:
                ans[i] = n3 * 3
                n3 += 1
            else:
                if n3q * 3 + n3r <= N:
                    ans[i] = n3q * 3 + n3r
                    if n3r == 1:
                        n3r = 2
                    else:
                        n3q += 1
                        n3r = 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
    elif n_even > int(N * 2 / 3):
        n3, n3q, n3r = 1, 0, 1
        for i in range(N):
            if dist[i] == 1:
                ans[i] = n3 * 3
                n3 += 1
            else:
                if n3q * 3 + n3r <= N:
                    ans[i] = n3q * 3 + n3r
                    if n3r == 1:
                        n3r = 2
                    else:
                        n3q += 1
                        n3r = 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
    else:
        n3, n31, n32 = 1, 0, 0
        for i in range(N):
            if dist[i] == 0:
                if n31 * 3 + 1 <= N:
                    ans[i] = n31 * 3 + 1
                    n31 += 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1
            else:
                if n32 * 3 + 2 <= N:
                    ans[i] = n32 * 3 + 2
                    n32 += 1
                else:
                    ans[i] = n3 * 3
                    n3 += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())

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

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

p = [0]*n

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

q = [0]

cnt = [1, 0]

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


ans = [0]*n

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

print(*ans)

Submission status: Accepted

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

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

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

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

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vのグループを持つ
    
    # 1 xor 3 = 2
    nxt_grp = grp^3
    
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    
    
    
if min(group_num) <= N//3:
    # どちらかのグループの要素数がN//3以下のとき，そのグループに0(mod3)を割り当てる
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in enumerate(group):
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in enumerate(group):
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    # 順番に1,2を割り当て，Nを超えたら0を割り当て
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            if idx_1>N:continue
            ans[i] = idx_1
            used[idx_1] = True
            idx_1 += 3
        else:
            if idx_2>N:continue
            ans[i] = idx_2
            used[idx_2] = True
            idx_2 += 3

    idx = 3
    for i in range(1,N+1):
        if ans[i]==0:
            while used[idx]:
                idx += 3
            ans[i] = idx
            used[idx] = True

    print(*ans[1:])

Submission status: Accepted

Solution code:
import queue

N = int(input())

# Adjacency matrix
e = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    e[a].append(b)
    e[b].append(a)

even_v = []
odd_v = []

is_reached = [False] * (N+1)
q = queue.Queue()
# [start vertex, total distance]
q.put([1, 0])

# BFS
while not q.empty():
    v, d = q.get()
    if is_reached[v]:
        continue
    is_reached[v] = True
    
    if d%2 == 0:
        even_v.append(v)
    else:
        odd_v.append(v)

    for tv in e[v]:
        q.put([tv, d+1])

# Remainder lists [1..N] mod 3
r1 = list(range(1, N+1, 3))
r2 = list(range(2, N+1, 3))
r3 = list(range(3, N+1, 3))

p = [0] * N
if len(even_v) <= len(r3):
    # Embed r3 in even_v
    for v in even_v:
        p[v-1] = r3.pop()
elif len(odd_v) <= len(r3):
    # Embed r3 in odd_v
    for v in odd_v:
        p[v-1] = r3.pop()
else:
    # Embed r1 in even_v
    for v in even_v:
        if not r1:
            break
        p[v-1] = r1.pop()
    # Embed r2 in odd_v
    for v in odd_v:
        if not r2:
            break
        p[v-1] = r2.pop()

# Collect unused vertexes
rv = []
rv.extend(r1)
rv.extend(r2)
rv.extend(r3)
for i, _ in enumerate(p):
    if p[i] == 0:
        p[i] = rv.pop()

ans = ' '.join(list(map(str, p)))
print(ans)

Submission status: Accepted

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

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

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

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

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vのグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    

if min(group_num) <= N//3:
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in enumerate(group):
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in enumerate(group):
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            if idx_1>N:continue
            ans[i] = idx_1
            used[idx_1] = True
            idx_1 += 3
        else:
            if idx_2>N:continue
            ans[i] = idx_2
            used[idx_2] = True
            idx_2 += 3

    idx = 3
    for i in range(1,N+1):
        if ans[i]==0:
            while used[idx]:
                idx += 3
            ans[i] = idx
            used[idx] = True

    print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]


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

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


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

for a, b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
try:
    trees[1].set_rank(1, None)
except:
    print(-1)
    exit()

group0 = [node.v for node in trees.values() if node.rank % 2 == 0]
group1 = [node.v for node in trees.values() if node.rank % 2]
x = [set(), set(), set()]
for i in range(1, N + 1):
    x[i % 3].add(i)
if len(group1) < len(group0):
    group1, group0 = group0, group1
result = {}
if len(group0) <= len(x[0]):
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    y = x[0] | x[1] | x[2]
    while group1 and y:
        result[group1.pop()] = y.pop()
else:
    while x[2] and group0:
        result[group0.pop()] = x[2].pop()
    while x[1] and group1:
        result[group1.pop()] = x[1].pop()
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    while group1 and x[0]:
        result[group1.pop()] = x[0].pop()
    if group0 or group1:
        print(-1)
        exit()

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

Submission status: Accepted

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
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
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 len(even) <= n // 3:
    odd, even = even, odd
if len(odd) <= n // 3:
    r = r2 + r1 + r0
else:
    r = r1 + r0 + r2
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

Submission status: Accepted

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
v=[0]*N
x=[0]*N
for i,j in AB:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
import sys
sys.setrecursionlimit(10**9)
def dfs(p):
    y=1 if x[p]==2 else 2
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            x[n]=y
            dfs(n)
v[0]=x[0]=1
dfs(0)
def f(x,a,b):
    p,q,r=0,0,1
    for i in range(N):
        if x[i]==a and p*3+1<=N:
            x[i]=p*3+1
            p+=1
        elif x[i]==b and q*3+2<=N:
            x[i]=q*3+2
            q+=1
        else:
            x[i]=r*3
            r+=1
if x.count(1)<=N//3:
    f(x,2,2)
elif x.count(2)<=N//3:
    f(x,1,1)
else:
    f(x,1,2)
print(*x)

Submission status: Accepted

Solution code:
import queue

N = int(input())

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

even_v = []
odd_v = []

is_reached = [False] * (N+1)
q = queue.Queue()
# [start vertex, total distance]
q.put([1, 0])

# BFS
while not q.empty():
    v, d = q.get()
    if is_reached[v]:
        continue
    is_reached[v] = True
    
    if d%2 == 0:
        even_v.append(v)
    else:
        odd_v.append(v)

    for tv in e[v]:
        q.put([tv, d+1])

r1 = list(range(1, N+1, 3))
r2 = list(range(2, N+1, 3))
r3 = list(range(3, N+1, 3))

ans = [0] * N
if len(even_v) <= len(r3):
    for v in even_v:
        ans[v-1] = r3.pop()
elif len(odd_v) <= len(r3):
    for v in odd_v:
        ans[v-1] = r3.pop()
else:
    for v in even_v:
        if not r1:
            break
        ans[v-1] = r1.pop()
    for v in odd_v:
        if not r2:
            break
        ans[v-1] = r2.pop()
rv = []
rv.extend(r1)
rv.extend(r2)
rv.extend(r3)
for i, p in enumerate(ans):
    if p == 0:
        ans[i] = rv.pop()

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

Submission status: Accepted

Solution code:
from collections import deque
N, *L = map(int, open(0).read().split())
E = [[] for i in range(N+1)]
for a,b  in zip(*[iter(L)]*2):
  E[a].append(b)
  E[b].append(a)
q = deque([1])
dist = [-1]*(N+1)
dist[1] = 0
dic = [[1],[]]
while q:
  u = q.popleft()
  for v in E[u]:
    if dist[v]==-1:
      dist[v] = dist[u]+1
      q.append(v)
      dic[dist[v]%2].append(v)

a = len(dic[0])
b = len(dic[1])
#print(dic)
seq = set(range(1,N+1))
ver = set(range(1,N+1))
ans = [0]*(N+1)
if a>N//3 and b>N//3:
  for i in range(1,N+1,3):
    v = dic[1].pop()
    ans[v] = i
  q = 0
  for i in range(2,N+1,3):
    v = dic[0].pop()
    ans[v] = i
  m = 3
  while dic[0]:
    v = dic[0].pop()
    ans[v] = m
    m += 3
  while dic[1]:
    v = dic[1].pop()
    ans[v] = m
    m += 3
elif a<=N//3:
  seq = set(range(1,N+1))
  m = 3
  while dic[0]:
    v = dic[0].pop()
    ans[v] = m
    seq.remove(m)
    m += 3
  seq = list(seq)
  while dic[1]:
    v = dic[1].pop()
    ans[v] = seq.pop()
else:
  seq = set(range(1,N+1))
  m = 3
  while dic[1]:
    v = dic[1].pop()
    ans[v] = m
    seq.remove(m)
    m += 3
  seq = list(seq)
  while dic[0]:
    v = dic[0].pop()
    ans[v] = seq.pop()
print(*ans[1:])