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:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

from collections import defaultdict
# d = defaultdict(list)


def resolve():
    global N, neighbor_list, color_list, count_dict
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    neighbor_list = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = sys.stdin.readline().split()
        a = int(a) - 1
        b = int(b) - 1
        neighbor_list[a].append(b)
        neighbor_list[b].append(a)

    logger.debug('{}'.format([]))

    color_list = [None for _ in range(N)]

    count_dict = defaultdict(int)

    dfs(0, 0)

    q0_list = list(range(3, N + 1, 3))
    q1_list = list(range(1, N + 1, 3))
    q2_list = list(range(2, N + 1, 3))
    ret_list = [0 for _ in range(N)]
    if count_dict[0] > N // 3 and count_dict[1] > N // 3:
        i_q0 = i_q1 = i_q2 = 0
        for i, c in enumerate(color_list):
            if c == 0:
                if i_q1 < len(q1_list):
                    ret_list[i] = q1_list[i_q1]
                    i_q1 += 1
                else:
                    ret_list[i] = q0_list[i_q0]
                    i_q0 += 1
            else:
                if i_q2 < len(q2_list):
                    ret_list[i] = q2_list[i_q2]
                    i_q2 += 1
                else:
                    ret_list[i] = q0_list[i_q0]
                    i_q0 += 1
        print(' '.join([str(c) for c in ret_list]))
        return

    if count_dict[0] <= N // 3:
        i_q0 = i_q1 = i_q2 = 0
        for i, c in enumerate(color_list):
            if c == 0:
                ret_list[i] = q0_list[i_q0]
                i_q0 += 1

        for i, c in enumerate(color_list):
            if c == 1:
                if i_q0 < len(q0_list):
                    ret_list[i] = q0_list[i_q0]
                    i_q0 += 1
                elif i_q1 < len(q1_list):
                    ret_list[i] = q1_list[i_q1]
                    i_q1 += 1
                else:
                    ret_list[i] = q2_list[i_q2]
                    i_q2 += 1
        print(' '.join([str(c) for c in ret_list]))
        return

    if count_dict[1] <= N // 3:
        i_q0 = i_q1 = i_q2 = 0
        for i, c in enumerate(color_list):
            if c == 1:
                ret_list[i] = q0_list[i_q0]
                i_q0 += 1

        for i, c in enumerate(color_list):
            if c == 0:
                if i_q0 < len(q0_list):
                    ret_list[i] = q0_list[i_q0]
                    i_q0 += 1
                elif i_q1 < len(q1_list):
                    ret_list[i] = q1_list[i_q1]
                    i_q1 += 1
                else:
                    ret_list[i] = q2_list[i_q2]
                    i_q2 += 1
        print(' '.join([str(c) for c in ret_list]))
        return


def dfs(i, color):
    global N, neighbor_list, color_list, count_dict
    color_list[i] = color
    count_dict[color] += 1
    for i_next in neighbor_list[i]:
        if color_list[i_next] is None:
            dfs(i_next, not color)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
1 2
1 3
3 4
3 5"""
        output = """1 2 5 4 3"""
        self.assertIO(input, output)

Submission status: Accepted

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(a)
  
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))

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

# print(m)

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

ans = [0] * n

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

Submission status: Accepted

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

num = [-1]*N
q = deque()
q.append((0, 0))
num[0] = 0
while q:
    temp = q.popleft()
    u = temp[0]
    n = temp[1]
    for v in E[u]:
        if num[v] >= 0:
            continue
        num[v] = (n+1)%2
        q.append((v, (n+1)%2))

ans = [0]*N
if sum(num) <= N//3 or N-sum(num) <= N//3:
    f = 1
    if N-sum(num) <= N//3:
        f = 0
    s = 1
    t = 3
    for i in range(N):
        if num[i] == f:
            ans[i] = t
            t += 3
    for i in range(N):
        if ans[i] == 0:
            ans[i] = s
            s += 1
            if s%3 == 0 and s < t:
                s += 1
else:
    s = 1
    t = 2
    u = 3
    for i in range(N):
        if num[i] == 0 and s <= N:
            ans[i] = s
            s += 3
        elif num[i] == 1 and t <= N:
            ans[i] = t
            t += 3
        else:
            ans[i] = u
            u += 3

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

dist = [10**10] * N
que = deque([(0, 0)])
while que:
    now, d = que.popleft()

    if dist[now] <= d:
        continue
    dist[now] = d

    for to in edges[now]:
        que.append((to, d + 1))

A = [i for i, d in enumerate(dist) if d % 2 == 0]
B = [i for i, d in enumerate(dist) if d % 2 == 1]

if len(A) > len(B):
    A, B = B, A

ans = [-1] * N
nums = set(range(1, N + 1))

if len(A) <= N // 3:
    mul = 1
    for i in A:
        ans[i] = 3 * mul
        nums.remove(3 * mul)
        mul += 1
    nums = list(nums)
    for i, n in zip(B, nums):
        ans[i] = n
else:
    mul = 1
    for c, i in enumerate(A):
        if c * 3 + 1 > N:
            ans[i] = mul * 3
            mul += 1
        else:
            ans[i] = c * 3 + 1
    for c, i in enumerate(B):
        if c * 3 + 2 > N:
            ans[i] = mul * 3
            mul += 1
        else:
            ans[i] = c * 3 + 2

print(*ans)

Submission status: Accepted

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)]
    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)
    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] = i+1
            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] = i+1
            i += 1
        print(*ans)
        return
    if len(ODD) <= len(EVEN):
        while mod1:
            index = EVEN.pop()
            ans[index] = mod1.pop()
        while mod2:
            index = ODD.pop()
            ans[index] = mod2.pop()
    else:
        while mod1:
            index = ODD.pop()
            ans[index] = mod1.pop()
        while mod2:
            index = EVEN.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: Accepted

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

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
    
    if len(A)<=n//3:
      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)
      exit()
    
    else:
      qq=deque([i for i in range(1,n+1,3)]+[i for i in range(3,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)
      exit()

Submission status: Accepted

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)
b=[-1]*n
b[0]=0
q=__import__("collections").deque([0])
while q:
	c=q.pop()
	for x in g[c]:
		if b[x]<0:b[x]=1-b[c];q.append(x)
lab=[-1]*n
Z=[i for i,x in enumerate(b) if x==0]
O=[i for i,x in enumerate(b) if x]
z=len(Z)
if z<=n//3 or n-z<=n//3:
	(L,H)=(Z,O) if z<=n//3 else (O,Z)
	a,b=1,3
	for i in L:lab[i]=b;b+=3
	for i in H:
		if b<=n:lab[i]=b;b+=3
		else:lab[i]=a;a+=1 if a%3==1 else 2
else:
	a,b,c=1,2,3
	for i in Z:
		if a<=n:lab[i]=a;a+=3
		else:lab[i]=c;c+=3
	for i in O:
		if b<=n:lab[i]=b;b+=3
		else:lab[i]=c;c+=3
print(*lab)

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter

n = int(input())
es = [[] for _ in range(n + 1)]

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

depth = [-1 for _ in range(n + 1)]
dq = deque([1])
depth[1] = 0

while dq:
	v = dq.pop()
	for e in es[v]:
		if depth[e] != -1:
			continue
		depth[e] = depth[v] + 1
		dq.append(e)

ans = [-1 for _ in range(n + 1)]	
cnt_dict = Counter([x % 2 for x in depth[1:]])

nums = [[i for i in range(1, n + 1) if i % 3 == 1], [i for i in range(1, n + 1) if i % 3 == 2], [i for i in range(1, n + 1) if i % 3 == 0]]
if cnt_dict[0] <= n // 3:
	for i in range(1, n + 1):
		if depth[i] % 2 == 0:
			ans[i] = nums[2].pop()
		else:
			if nums[0]:
				ans[i] = nums[0].pop()
			elif nums[1]:
				ans[i] = nums[1].pop()
			else:
				ans[i] = nums[2].pop()
elif cnt_dict[1] <= n // 3:
	for i in range(1, n + 1):
		if depth[i] % 2 == 1:
			ans[i] = nums[2].pop()
		else:
			if nums[0]:
				ans[i] = nums[0].pop()
			elif nums[1]:
				ans[i] = nums[1].pop()
			else:
				ans[i] = nums[2].pop()
else:
	for i in range(1, n + 1):
		if depth[i] % 2 == 0:
			if nums[0]:
				ans[i] = nums[0].pop()
			else:
				ans[i] = nums[2].pop()
		else:
			if nums[1]:
				ans[i] = nums[1].pop()
			else:
				ans[i] = nums[2].pop()

print(*ans[1:])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [-1]*n
    d[0] = 0
    q = deque([0])
    while q:
        x = q.popleft()
        nd = d[x]^1
        for y in v[x]:
            if d[y] < 0:
                d[y] = nd
                q.append(y)
    n1 = sum(d)
    n0 = len(d)-n1
    if n1 > n0:
        for i in range(n):
            d[i] ^= 1
        n0,n1 = n1,n0
    p = [(n+2)//3, (n+1)//3, n//3]
    k = [1,2,3]
    ans = [0]*n
    if n1 >= p[1]:
        for i in range(n):
            di = d[i]
            if not p[di]:
                di = 2
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    else:
        for i in range(n):
            di = d[i]
            if di == 1:
                di = 2
            while not p[di]:
                di += 1
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    print(*ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if n < 4:
        print(*range(1,n+1),sep = " ")
        return
    d = [-1]*n
    d[0] = 0
    q = deque([0])
    while q:
        x = q.popleft()
        nd = d[x]^1
        for y in v[x]:
            if d[y] < 0:
                d[y] = nd
                q.append(y)
    n1 = sum(d)
    n0 = len(d)-n1
    if n1 > n0:
        for i in range(n):
            d[i] ^= 1
        n0,n1 = n1,n0
    p = [(n+2)//3, (n+1)//3, n//3]
    k = [1,2,3]
    ans = [0]*n
    if n1 >= p[1]:
        for i in range(n):
            di = d[i]
            if not p[di]:
                di = 2
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    else:
        for i in range(n):
            di = d[i]
            if di == 1:
                di = 2
            while not p[di]:
                di += 1
            ans[i] = k[di]
            k[di] += 3
            p[di] -= 1
    print(*ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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)
b=[-1]*n
b[0]=0
q=[0]
while q:
	c=q.pop()
	for x in g[c]:
		if b[x]<0:b[x]=1-b[c];q.append(x)
lab=[-1]*n
Z=[i for i,x in enumerate(b) if x==0]
O=[i for i,x in enumerate(b) if x]
z,o=len(Z),len(O)
if z<=n//3 or o<=n//3:
	(L,H)=(Z,O) if z<=n//3 else (O,Z)
	a,b=1,3
	for i in L:lab[i]=b;b+=3
	for i in H:
		if b<=n:lab[i]=b;b+=3
		else:lab[i]=a;a+=1 if a%3==1 else 2
else:
	a,b,c=1,2,3
	for i in Z:
		if a<=n:lab[i]=a;a+=3
		else:lab[i]=c;c+=3
	for i in O:
		if b<=n:lab[i]=b;b+=3
		else:lab[i]=c;c+=3
print(*lab)

Submission status: Accepted

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
	for i,x in enumerate(tr):
		if x==1-f:
			if thr<=n:
				lab[i]=thr
				thr+=3
			else:
				lab[i]=onetwo
				onetwo+=1 if onetwo%3==1 else 2
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: Accepted

Solution code:
from collections import defaultdict, Counter, deque

N, = list(map(int, input().split()))

g = defaultdict(list)
for i in range(N - 1):
    u, v = list(map(int, input().split()))
    g[u].append(v)
    g[v].append(u)

# BFS to label each node with its level (bipartite 2-coloring)
source = 1
dist = {}
q = deque()
q.append(source)
dist[source] = 0
while q:
    node = q.popleft()
    level = dist[node]
    for nbr in g[node]:
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = level + 1

mod1 = list(range(1, N + 1, 3))
mod2 = list(range(2, N + 1, 3))
mod0 = list(range(3, N + 1, 3))

# Count the number of nodes on odd and even levels
parityCounts = Counter(level % 2 for level in dist.values())

assign = {}
# Since 3 is odd, any distance of 3 will connect two nodes of different parity levels
if min(parityCounts[0], parityCounts[1]) <= len(mod0):
    # Either the odd or even levels is small enough to be completely 0 mod 3 which can connect to anything else
    parityOfSmaller = min([0, 1], key=lambda k: parityCounts[k])
    for i in range(1, N + 1):
        if dist[i] % 2 == parityOfSmaller:
            assign[i] = mod0.pop()
        else:
            if mod1:
                assign[i] = mod1.pop()
            elif mod2:
                assign[i] = mod2.pop()
            elif mod0:
                assign[i] = mod0.pop()
else:
    # We want to assign all (1 mod 3) to one parity and all (2 mod 3) to another parity
    # Then the sum will always be a multiple of 3
    # The two levels should always have enough nodes to consume all of mod1 and mod2
    # Anything else can be padded with mod0
    assert len(mod0) <= len(mod2) <= len(mod1)

    if parityCounts[0] < parityCounts[1]:
        assert len(mod2) <= parityCounts[0]
        assert len(mod1) <= parityCounts[1]
        parityToMod = {0: mod2, 1: mod1}
    else:
        assert len(mod1) <= parityCounts[0]
        assert len(mod2) <= parityCounts[1]
        parityToMod = {0: mod1, 1: mod2}

    for i in range(1, N + 1):
        mod = parityToMod[dist[i] % 2]
        if mod:
            assign[i] = mod.pop()
        else:
            assign[i] = mod0.pop()

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

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 2部グラフ
# 二部グラフ

N = int(readline())

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

DIST = [-1] * (N+1)
STACK = [1]
DIST[1] = 0

'''
距離を求めて、2で割る
木ならこれでOK

while STACK:
    v = STACK.pop()

    for w in E[v]:
        if DIST[w] == -1:
            DIST[w] = DIST[v] + 1
            STACK.append(w)
'''

COLOR = [None] * (N + 1)


def setColor(v, c):
    COLOR[v] = c
    for w in E[v]:
        if COLOR[w] == None:
            setColor(w, -c)


setColor(1, 1)

EVEN = [i for i, x in enumerate(COLOR) if x == 1 and i > 0]
ODD = [i for i, x in enumerate(COLOR) if x == -1 and i > 0]

listN = list(range(1, N + 1))
mod1 = deque(listN[0::3])
mod2 = deque(listN[1::3])
mod0 = deque(listN[2::3])

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


def assign(target, arr1, arr2=[], arr3=[]):
    source = [arr1, arr2, arr3]
    idx = 0
    for e in target:
        if len(source[idx]) == 0:
            idx += 1

        ANS[e] = source[idx].pop()
    return 0


if len(EVEN) <= len(mod0):
    assign(EVEN, mod0)
    assign(ODD, mod0, mod1, mod2)
elif len(ODD) <= len(mod0):
    assign(ODD, mod0)
    assign(EVEN, mod0, mod1, mod2)
else:
    assign(EVEN, mod1, mod0)
    assign(ODD, mod2, mod0)

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

# 頂点1からの距離が奇数:1、偶数:0
group = [False] * N
# 親ノードを格納する
parents = list(range(N))
stack = [0]

# ノードの選択
while stack:
    p = stack.pop()
    # 子ノードの選択
    for c in node[p]:
        # 親ノードも選択されるので、その場合は飛ばす
        if c != parents[p]:
            # 子ノードの親を自分にする
            parents[c] = p
            # 子ノードのグループを自分と逆に設定する
            group[c] = not group[p]
            stack.append(c)

p = [0] * N
three = 3
if group.count(True) <= N // 3:
    other = 1
    # Trueのところには３の倍数を、Falseにはそれ以外を
    for i in range(N):
        if not group[i] and other <= N:
            p[i] = other
            other += other % 3
        else:
            p[i] = three
            three += 3
elif group.count(False) <= N // 3:
    other = 1
    # Trueのところには３の倍数を、Falseにはそれ以外を
    for i in range(N):
        if group[i] and other <= N:
            p[i] = other
            other += other % 3
        else:
            p[i] = three
            three += 3

else:
    one, two = 1, 2
    # Trueのところには３の倍数を、Falseにはそれ以外を
    for i in range(N):
        if not group[i] and one <= N:
            p[i] = one
            one += 3
        elif group[i] and two <= N:
            p[i] = two
            two += 3
        else:
            p[i] = three
            three += 3
print(" ".join(map(str, p)))

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
x=[[],[],[]]
for i in range(n):
    x[i%3]+=i+1,
for a,b in zip(*[iter(t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
a=[-1]*n
p=a[:]
p[0]=0
s=[0]
c=[1,0]
while s:
    v=s.pop()
    for w in e[v]:
        if p[w]<0:
            p[w]=p[v]^1
            c[p[w]]+=1
            s+=w,
if min(c)<=n//3:
    x[0]+=x[1]
    f=c[0]<=n//3
    for i,v in enumerate(p):
        j=(v==f)-1
        a[i]=x[j if x[j]else-1].pop()
else:
    for i,v in enumerate(p):
        a[i]=x[v if x[v]else-1].pop()
print(*a)

Submission status: Accepted

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

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

    
    use = [-1 for _ in range(N)]
    d = [[0],[]]
    use[0] = 0
    q = deque([0])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if use[fol] == -1:
                use[fol] = (use[now]+1)%2
                q.append(fol)
                d[use[fol]].append(fol)

    ans = [0 for _ in range(N)]
    b = [False for _ in range(N)]
    if len(d[0]) <= N//3:
        l = len(d[0])
        for i in range(l):
            ans[d[0][i]] = 3*i+3
            b[3*i+2] = True
        t = 0
        for num in d[1]:
            while b[t]:
                t += 1
            ans[num] = t+1
            b[t] = True
    elif len(d[1]) <= N//3:
        l = len(d[1])
        for i in range(l):
            ans[d[1][i]] = 3*i+3
            b[3*i+2] = True
        t = 0
        for num in d[0]:
            while b[t]:
                t += 1
            ans[num] = t+1
            b[t] = True
    else:
        l = len(d[0])
        t = 0
        for i in range(l):
            if i < (N-1)//3+1:
                ans[d[0][i]] = 3*i+1
                b[3*i] = True
            else:
                ans[d[0][i]] = 3*t+3
                b[3*t+2] = True
                t += 1
        l = len(d[1])
        for i in range(l):
            if i < (N-2)//3+1:
                ans[d[1][i]] = 3*i+2
                b[3*i+1] = True
            else:
                ans[d[1][i]] = 3*t+3
                b[3*t+2] = True
                t += 1
    
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

b = [[] for i in range(n)]
a1=[]
a2=[]
ans=[0]*n
for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)
    b[a[i][1]-1].append(a[i][0]-1)

import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)
        a1.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1
                    if dis[y]%2==0:
                        a1.append(y)
                    else:
                        a2.append(y)
        return a1,a2
    return bfs()

tree(0)

j = 0
k = 0
if min(len(a1),len(a2))<=n//3:
    if len(a1)<=n//3:
        for i in range(1,n+1):
            if i<=len(a1)*3 and i%3==0 and j<=len(a1)-1:
                ans[a1[j]]=i
                j+=1
            else:
                ans[a2[k]]=i
                k+=1
    else:
        for i in range(1,n+1):
            if i<=len(a2)*3 and i%3==0 and j<=len(a2)-1:
                ans[a2[j]]=i
                j+=1
            else:
                ans[a1[k]]=i
                k+=1

else:
    for i in range(1,n+1):
        if i%3==1:
            ans[a1[j]]=i
            j+=1
        elif i%3==2:
            ans[a2[k]] = i
            k += 1
        else:
            continue

    for i in range(3,n+1,3):
        if j<=len(a1)-1:
            ans[a1[j]]=i
            j+=1
        else:
            ans[a2[k]] = i
            k += 1


print(*ans)