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 collections
n = int(input())
one = collections.deque([1])
two = collections.deque([])
three = collections.deque([])
graph = [[] for _ in range(n)]

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    if i % 3 == 0: two.append(i + 2)
    elif i % 3 == 1: three.append(i + 2)
    else: one.append(i + 2)

que = collections.deque([0])
num = [0] * n
dist = [-1] * n
parity = [0] * 2
dist[0] = 0
flag = True
while len(que) != 0:
    i = que.popleft()
    parity[dist[i] % 2] += 1
    for j in graph[i]:
        if dist[j] != -1: continue
        dist[j] = dist[i] + 1
        que.append(j)

if parity[0] <= n // 3 or parity[1] <= n // 3:
    rem = 0 if parity[0] < parity[1] else 1
    for i, v in enumerate(dist):
        if v % 2 == rem:
            num[i] = str(three.popleft())
        else:
            if len(one) != 0: num[i] = str(one.popleft())
            elif len(two) != 0: num[i] = str(two.popleft())
            else: num[i] = str(three.popleft())
else:
    for i, v in enumerate(dist):
        if v % 2 == 0:
            if len(one) != 0: num[i] = str(one.popleft())
            elif len(three) != 0: num[i] = str(three.popleft())
            else:
                flag = False
                break
        else:
            if len(two) != 0: num[i] = str(two.popleft())
            elif len(three) != 0: num[i] = str(three.popleft())
            else:
                flag = False
                break

print(' '.join(num))

Submission status: Accepted

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

def bfs():
    q = deque([0])
    color = [0]*N
    color[0] = 1
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
    
    return color

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)
    
cnt = [0]*3

for i in range(1, N+1):
    cnt[i%3] += 1

color = bfs()
m = color.count(1)
ans = [-1]*N

if m<=cnt[0]:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==1:
            ans[i] = c0
            c0 += 3
    
    for i in range(N):
        if color[i]==-1:
            if c0<=N:
                ans[i] = c0
                c0 += 3
            else:
                if c1<=N:
                    ans[i] = c1
                    c1 += 3
                else:
                    ans[i] = c2
                    c2 += 3
elif m>=N-cnt[0]:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==-1:
            ans[i] = c0
            c0 += 3
    
    for i in range(N):
        if color[i]==1:
            if c0<=N:
                ans[i] = c0
                c0 += 3
            else:
                if c1<=N:
                    ans[i] = c1
                    c1 += 3
                else:
                    ans[i] = c2
                    c2 += 3
else:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==1:
            if c1<=N:
                ans[i] = c1
                c1 += 3
            else:
                ans[i] = c0
                c0 += 3
        
    for i in range(N):
        if color[i]==-1:
            if c0<=N:
                ans[i] = c0
                c0 += 3
            else:
                ans[i] = c2
                c2 += 3

print(*ans)

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    from itertools import chain
    import sys
    input = sys.stdin.readline

    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    bipartite = [-1] * N
    bipartite[0] = 0

    dq = deque([0])
    while dq:
        v = dq.popleft()
        nb = bipartite[v] ^ 1
        for u in graph[v]:
            if ~bipartite[u]: continue
            bipartite[u] = nb
            dq.append(u)

    s0 = bipartite.count(0)
    s1 = N - s0

    it1 = iter(range(1, N + 1, 3))
    it2 = iter(range(2, N + 1, 3))
    it3 = iter(range(3, N + 1, 3))
    it123 = chain(it1, it2, it3)
    it13 = chain(it1, it3)
    it23 = chain(it2, it3)

    ans = [-1] * N
    K = N // 3
    if s0 <= K:
        for v in range(N):
            if bipartite[v] == 0:
                ans[v] = next(it3)
            else:
                ans[v] = next(it123)  # 余った3をこちらで消費するので12ではなく123
    elif s1 <= K:
        for v in range(N):
            if bipartite[v] == 1:
                ans[v] = next(it3)
            else:
                ans[v] = next(it123)
    else:
        for v in range(N):
            if bipartite[v] == 0:
                ans[v] = next(it13)
            else:
                ans[v] = next(it23)

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
m = map(int,read().split())
AB = zip(m,m)
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
dist = [-1] * (N+1)
stack = [1]
dist[1] = 0
while stack:
    v = stack.pop()
    for w in graph[v]:
        if dist[w] == -1:
            dist[w] = dist[v] + 1
            stack.append(w)
 
ev = [i for i,x in enumerate(dist) if x % 2 == 0 and i > 0]
od = [i for i,x in enumerate(dist) if x % 2 == 1 and i > 0]
 
def make_perm(N, ev, od, x0, x1, x2, y0, y1, y2):
    assert len(ev) == x0 + x1 + x2
    assert len(od) == y0 + y1 + y2
    P = [0] * (N+1)
    for i in ev:
        if x0:
            P[i] = (x0 + y0) * 3
            x0 -= 1
            continue
        if x1:
            P[i] = (x1 + y1) * 3 - 2
            x1 -= 1
            continue
        if x2:
            P[i] = (x2 + y2) * 3 - 1
            x2 -= 1
            continue
    for i in od:
        if y0:
            P[i] = (x0 + y0) * 3
            y0 -= 1
            continue
        if y1:
            P[i] = (x1 + y1) * 3 - 2
            y1 -= 1
            continue
        if y2:
            P[i] = (x2 + y2) * 3 - 1
            y2 -= 1
            continue
    return P[1:]
 
def solve(N, ev, od):
    x0 = N // 3
    x1 = (N+2) // 3
    x2 = (N+1) // 3
    perm = [0] * (N+1)
    LE = len(ev)
    LO = len(od)
    if LE <= x0:
        return make_perm(N, ev, od, LE, 0, 0, x0-LE, x1, x2)
    if LO <= x0:
        return make_perm(N, ev, od, x0-LO, x1, x2, LO, 0, 0)
    if LE == x1:
        return make_perm(N, ev, od, 0, x1, 0, x0, 0, x2)
    if LO == x1:
        return make_perm(N, ev, od, x0, 0, x2, 0, x1, 0)
    # どちらも x1 よりたくさんある
    return make_perm(N, ev, od, LE-x1, x1, 0, LO-x2, 0, x2)
 
P = solve(N, ev, od)
print(' '.join(map(str, P)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    return 
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if i % 3 == 0:
            if r:
                ans[r.pop()] = i
            elif b:
                ans[b.pop()] = i
print(*ans)

Submission status: Accepted

Solution code:
# coding: utf-8

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

def run(cur, tr, dist, d=1, pre=-1, recur=1, save_recur = []):
    for node in tr[cur]:
        if node == pre:continue
        dist[d].append(node)
        if recur >500:
            dic_ = {'cur':node, 'tr': tr, 'dist': dist,
                              'd': (d + 1) % 2, 'pre': cur, 'recur': recur + 1}
            save_recur.append(dic_)
            return None
        run(node, tr, dist, (d+1)%2, pre=cur, recur=recur+1, save_recur=save_recur)
    return None

if __name__ == '__main__':
    # generate dict
    tr = {}
    for line in ab:
        if line[0] not in tr.keys():
            tr[line[0]] = [line[1]]
        else:
            tr[line[0]].append(line[1])
        if line[1] not in tr.keys():
            tr[line[1]] = [line[0]]
        else:
            tr[line[1]].append(line[0])

    dist = {0: [1], 1: []}
    save_rec = []
    run(1, tr, dist, save_recur=save_rec)

    while True:
        save_rec2 = save_rec
        save_rec = []
        for dict in save_rec2:
            run(dict['cur'], dict['tr'], dict['dist'], dict['d'],
                dict['pre'], dict['recur'],save_recur = save_rec)
        if save_rec == []:break


    perm = [0] * (N+1)
    rem1_max, rem2_max, rem0_max = int(N/3),int(N/3),int(N/3)
    if N % 3 == 1:
        rem1_max +=1
    if N % 3 == 2:
        rem1_max += 1
        rem2_max += 1
    if (len(dist[0]) <= N/3) | (len(dist[0]) >= 2*N/3):
        bool = int(len(dist[0]) <= N/3)
        h0 = 1
        for k in dist[1-bool]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3*i for i in range(h0, rem0_max+1)] + [3*i+1 for i in range(0, rem1_max)] + [3*i+2 for i in range(0, rem2_max)]
        for k, val in zip(dist[bool], nums):
            perm[k] = val
    else:
        n = int(N/3)
        if N % 3 == 2:
            n += 1
        h1 = 0
        h2 = 0
        idx = 0
        bool = int((len(dist[0]) > len(dist[1])))
        for alpha in range(n):
            even = dist[bool][idx]
            perm[even] = alpha * 3 + 1
            odd = dist[1-bool][idx]
            perm[odd] = alpha * 3 + 2
            idx += 1
        h0 = 1
        for k in dist[1-bool][idx:]:
            perm[k] = 3 * h0
            h0 += 1
        nums = [3 * i for i in range(h0, rem0_max+1)] + [3 * i + 1 for i in range(n, rem1_max)] + [3 * i + 2 for i in range(n, rem2_max)]

        for h, k in enumerate(dist[bool][idx:]):
            perm[k] = nums[h]
    print(" ".join(list(map(str, perm[1:]))))

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    T = {i: set() for i in range(1, n+1)}
    for ab in map(str.split, args[1:]):
        a, b = map(int, ab)
        T[a].add(b)
        T[b].add(a)

    R = set()
    B = set()

    stack = [(1, 0)]
    while stack:
        i, d = stack.pop()
        if i in R or i in B:
            continue
        if d % 2:
            R.add(i)
        else:
            B.add(i)
        for j in T[i]:
            stack.append((j, d+1))

    R, B = (R, B) if len(R) < len(B) else (B, R)

    ret = [0]*(n+1)
    if len(R) <= n//3:
        for i in range(1, n+1):
            if i % 3:
                ret[B.pop()] = i
            else:
                ret[R.pop() if R else B.pop()] = i
    else:
        for i in range(1, n+1, 3):
            ret[R.pop()] = i
        for i in range(2, n+1, 3):
            ret[B.pop()] = i
        for i in range(3, n+1, 3):
            ret[R.pop() if R else B.pop()] = i

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[] for _ 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)

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in G[now] :
        if col[i] == -1 :
            col[i] = (col[now] + 1)%2
            stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
else :
    mods = deque(mod1 + mod0 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()

print(*ans)

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

a = sum(flag)
b = n-a

one = []
two = []
three = []
for i in range(1, n+1):
    if i%3 == 0:
        three.append(i)
    elif i%3 == 1:
        one.append(i)
    else:
        two.append(i)
k = n//3
ans = [0]*n
if k<a and k<b:
    for i in range(n):
        if flag[i]:
            if one:
                ans[i] = one.pop()
            else:
                ans[i] = three.pop()
        else:
            if two:
                ans[i] = two.pop()
            else:
                ans[i] = three.pop()
else:
    #1
    if k >= a:
        for i in range(n):
            if flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if not flag[i]:
                ans[i] = res.pop()
    # 0
    else:
        for i in range(n):
            if not flag[i]:
                ans[i] = three.pop()
        res = one + two + three
        for i in range(n):
            if flag[i]:
                ans[i] = res.pop()
print(*ans)

Submission status: Accepted

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

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

mod = 10**9 + 7

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

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

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

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

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

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

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

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

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

ans = [0]*N

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

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

print(*ans)

Submission status: Accepted

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


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


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


ans = []
x12, x3 = X[0] + X[1], X[2]
if colors.count(0) <= N // 3:
    for color in colors:
        if color == 0:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

elif colors.count(1) <= N // 3:
    for color in colors:
        if color == 1:
            ans.append(x3.pop())
        elif x12:
            ans.append(x12.pop())
        else:
            ans.append(x3.pop())

else:
    for color in colors:
        if X[color]:
            ans.append(X[color].pop())
        else:
            ans.append(X[2].pop())

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

Submission status: Accepted

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

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

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

categorize2g(-1, 0, 0)

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

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

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

Submission status: Accepted

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

n = int(input())

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

odd = []
even = []

ans = [-1] * n
def dfs(x, last = -1, d = 0):
    if d%2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:
            continue
        dfs(nxt, x, d + 1)

dfs(0)

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

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

else:
    for num in nums[1]:
        ans[odd.pop()] = num
    for num in nums[2]:
        ans[even.pop()] = num
    rest = nums[0] + nums[1] + nums[2]
    for num in rest:
        if len(odd):
            ans[odd.pop()] = num
        elif len(even):
            ans[even.pop()] = num

print(*ans)

Submission status: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(10 ** 6)
n = int(input())
 
edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even =[]
nums = [[],[],[]]
for i in range(1,n+1):
    nums[i % 3].append(i)
 
def dfs(x, last = -1, d = 0):
    if d % 2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:continue
        dfs(nxt, x, d + 1)
 
for i in range(n-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[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 num in nums[1]:
        ans[even.pop()] = num
    for num in nums[2]:
        ans[odd.pop()] = num
    rest = nums[0]
    for even_node in even:
        ans[even_node] = rest.pop()
    for odd_node in odd:
        ans[odd_node] = rest.pop()
 
print(*ans)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 1(mod 3)のグループと2(mod 3)のグループを先に決める
N = ir()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

root = 1
rank = [0] * (N+1) # 1-indexed
rank[1] = 1
parent = [0] * (N+1) # 1-indexed
stack = [root]
while stack:
    cur = stack.pop()
    r = rank[cur]
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        rank[next] = r + 1
        stack.append(next)

counter = [0, 0]
for x in rank[1:]:
    counter[x%2] += 1
num0mod3 = N // 3
num1mod3 = (N+2) // 3
num2mod3 = (N+1) // 3
answer = [0] * (N+1)
if max(counter) >= num1mod3 + num2mod3:
    #この時ここに1mod3、2mod3を全部入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 1
            if cur % 3 == 0:
                cur += 1
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
else:
    #ここではcounterの多い方にnum1mod3を入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 2
    for i in range(1, N+1):
        if rank[i] % 2 == 1-index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)

print(*answer[1:])

Submission status: Accepted

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

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

"""

import collections
import itertools
import operator


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

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

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

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

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

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

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


n = onem()

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

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

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

tr = n // 3

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

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

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


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



print(jo(po))

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()