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:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

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


main()

Submission status: Accepted

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


def dfs(v, step):
    global node0, node1
    if step & 1:
        color[v] = 1
        node1 += 1
    else:
        color[v] = 0
        node0 += 1
    for nv in edge[v]:
        if color[nv] is None:
            dfs(nv, step + 1)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
color = [None] * N
node0 = node1 = 0
dfs(0, 0)

ans = [None] * N
num0 = N // 3
num1 = N // 3 + (N % 3 >= 1)
num2 = N // 3 + (N % 3 == 2)
if node0 > num0 and node1 > num0:
    cur = 0
    while num1 > 0:
        if color[cur] == 1:
            ans[cur] = 3 * num1 - 2
            num1 -= 1
        cur += 1
    cur = 0
    while num2 > 0:
        if color[cur] == 0:
            ans[cur] = 3 * num2 - 1
            num2 -= 1
        cur += 1
elif node0 <= num0:
    cur = 0
    while node0 > 0:
        if color[cur] == 0:
            ans[cur] = 3 * num0
            num0 -= 1
            node0 -= 1
        cur += 1
else:
    cur = 0
    while node1 > 0:
        if color[cur] == 1:
            ans[cur] = 3 * num0
            num0 -= 1
            node1 -= 1
        cur += 1

cur = 0
while num0 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num0
        num0 -= 1
    cur += 1
while num1 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num1 - 2
        num1 -= 1
    cur += 1
while num2 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num2 - 1
        num2 -= 1
    cur += 1


print(*ans)

Submission status: Accepted

Solution code:

"""
Writer:SPD_9X2

木を2色で塗り分ける(交互に)

mod3で、
赤/青
10/20
20/10
120/0
0/120s
の4通りの分け方を試せばよい

絶対OKな証明
入る場合→入れればよい
入らない場合→mod0は必ずmod1,mod2以下の数。
mod0を入れても空きがあるとまずいけど、差は1以下なのでその場合はmod1が必ず入る
→おわり

"""


import sys
from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis

N = int(input())

lis = [[] for i in range(N)]
for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

dis,plis = NC_Dij(lis,0)

use = [1,2,3]

flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3
    if nex > N:
        nex = use[2]
        use[2] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()

use = [2,1,3]
flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3
    if nex > N:
        nex = use[2]
        use[2] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()

use = [3,1,2]
flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3
    if nex > N and nex % 3 == 1:
        nex = use[2]
        use[2] += 3
    if nex > N and nex % 3 == 2:
        nex = use[0]
        use[0] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()


use = [1,3,2]
flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3

    if nex > N and nex % 3 == 1:
        nex = use[2]
        use[2] += 3
    if nex > N and nex % 3 == 2:
        nex = use[1]
        use[1] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()



print (-1)

Submission status: Accepted

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

#場合分け
if count_even > n/3 and count_odd > n/3:
    #この場合、普通にやる
    for i in range(1,len(dist)):
        if dist[i] % 2 == 1:
            if index_2 < len(rem_2):
                ans.append(rem_2[index_2])
                index_2 += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
        else:
            if index_1 < len(rem_1):
                ans.append(rem_1[index_1])
                index_1 += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
elif count_even <= n/3:
    #1からの距離が偶数のところが全体の1/3を閉めない場合
    #そこに全部3の倍数を入れてしまえば、題意を満たす
    li = rem_1 + rem_2
    index = 0
    for i in range(1,len(dist)):
        if dist[i] % 2 == 0:
            ans.append(rem_0[index_0])
            index_0 += 1
        else:
            if index < len(li):
                ans.append(li[index])
                index += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
else:
    ##1からの距離が奇数のところが全体の1/3を閉めない場合
    #そこに全部3の倍数を入れてしまえば、題意を満たす
    li = rem_1 + rem_2
    index = 0
    for i in range(1,len(dist)):
        if dist[i] % 2 == 1:
            ans.append(rem_0[index_0])
            index_0 += 1
        else:
            if index < len(li):
                ans.append(li[index])
                index += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
for i in ans:
    print(i, end=" ")

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
n = int(readline())

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)

colors = [0] * (n+1)
 
colors[1] = 1
 
todo = []
for to in g[1]:
    todo.append([to, -1])
 
while todo:
    node, color = todo.pop()
 
    if colors[node] != 0:
        continue
 
    colors[node] = color
    new_color = -color
    for to in g[node]:
        if colors[to] != 0:
            continue
        todo.append([to, new_color])
ans = [0]*(n+1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1,n+1):
    if i%3==1:
        t1.append(i)
    elif i%3==2:
        t2.append(i)
    else:
        t0.append(i)
black = 0
for i in colors[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if colors[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
elif black >= n-n//3:
    for i in range(1,n+1):
        if colors[i] == -1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if colors[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])

Submission status: Accepted

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

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

dfs(1)
bl = cl.count(1)
wh = N - bl
res = [0] * (N + 1)
nm = [[] for _ in range(3)]
for i in range(1, N + 1): nm[i % 3].append(i)
#print(cl)
if bl <= N // 3:
  for i in range(1, N + 1):
    if cl[i]:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
if wh <= N // 3:
  for i in range(1, N + 1):
    if cl[i] == 0:
      res[i] = nm[0].pop()
    else:
      if len(nm[1]): res[i] = nm[1].pop()
      elif len(nm[2]): res[i] = nm[2].pop()
      else: res[i] = nm[0].pop()
  print(*res[1: ])
  exit(0)
#print(nm)
#print(cl, nm)
f = 0
for i in range(1, N + 1):
  if cl[i]:
    if len(nm[1]):
      res[i] = nm[1].pop()
    else:
      res[i] = nm[0].pop()
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      res[i] = nm[0].pop()

print(*res[1: ])

Submission status: Accepted

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

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

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

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

coloring(1, 1)

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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


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

colors = [-1] * n

colors[0] = 0

todo = []
for to in edges[0]:
    todo.append([to, 1])

while todo:
    node, color = todo.pop()

    if colors[node] != -1:
        continue

    colors[node] = color
    new_color = 1 - color
    for to in edges[node]:
        if colors[to] != -1:
            continue
        todo.append([to, new_color])

red_count = sum(colors)  # 1
blue_count = n - red_count  # 0

ans = [0] * n

num3s = list(range(3, n+1, 3))
nums = [num for num in range(1, n+1) if num % 3 != 0]

if red_count <= n // 3:
    for node in range(n):
        if colors[node] == 1:
            ans[node] = num3s.pop()

        else:
            if nums:
                num = nums.pop()
            else:
                num = num3s.pop()
            ans[node] = num


elif blue_count <= n // 3:
    for node in range(n):
        if colors[node] == 0:
            ans[node] = num3s.pop()

        else:
            if nums:
                num = nums.pop()
            else:
                num = num3s.pop()
            ans[node] = num

else:
    num1s = list(range(1, n+1, 3))
    num2s = list(range(2, n+1, 3))

    for node in range(n):
        if colors[node] == 1:
            if num1s:
                num = num1s.pop()
            else:
                num = num3s.pop()
            ans[node] = num

        else:
            if num2s:
                num = num2s.pop()
            else:
                num = num3s.pop()
            ans[node] = num

print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
data = [[] for i in range(N)]

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

stack = [0]
d = [-1] * N
d[0] = 0

while stack:
    x = stack.pop()
    for y in data[x]:
        if d[y] != -1:
            continue
        d[y] = d[x] + 1
        stack.append(y)

mod = [[],[]]
for i in range(N):
    mod[d[i]%2].append(i)

ans = [0]*N

p = 1
q = 2
r = 3
if len(mod[0]) > N//3 and len(mod[1]) > N//3:
    for k in mod[0]:
        if p <= N:
            ans[k] = p
            p += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[1]:
        if q <= N:
            ans[l] = q
            q += 3
        else:
            ans[l] = r
            r += 3
    
elif len(mod[0]) > N//3:
    for k in mod[0]:
        if p <= N:
            ans[k] = p
            p += 3
        elif q <= N:
            ans[k] = q
            q += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[1]:
        ans[l] = r
        r += 3

else:
    for k in mod[1]:
        if p <= N:
            ans[k] = p
            p += 3
        elif q <= N:
            ans[k] = q
            q += 3
        else:
            ans[k] = r
            r += 3
    for l in mod[0]:
        ans[l] = r
        r += 3

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque


def solve(n, ab_list):
    g = [[] for _ in range(n + 1)]
    for a, b in ab_list:
        g[a].append(b)
        g[b].append(a)
    # start from 1
    d_list = [-1] * (n + 1)
    d_list[1] = 0
    queue = deque([1])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if d_list[q] == -1:
                d_list[q] = d_list[p] + 1
                queue.append(q)
    # print(d_list)
    cnt_2 = [0] * 6
    for i in range(1, n + 1):
        cnt_2[d_list[i] % 2] += 1

    if cnt_2[0] <= cnt_2[1]:
        min_01 = 0
    else:
        min_01 = 1

    min_sum = cnt_2[min_01]
    if min_sum <= n // 3:
        res_list = [0] * n
        list_3 = [3 * (k + 1) for k in range(min_sum)]
        list_other = [k for k in range(1, n + 1) if k % 3 != 0] + [3 * (k + 1) for k in range(min_sum, n // 3)]
        for i in range(1, n + 1):
            if d_list[i] % 2 == min_01:
                res_list[i - 1] = list_3.pop()
            else:
                res_list[i - 1] = list_other.pop()
    else:
        res_list = [0] * n
        add_1 = min_sum - (n + 2) // 3
        list_1 = [k + 1 for k in range(n) if k % 3 == 0] + [3 * (k + 1) for k in range(add_1)]
        list_2 = [k + 1 for k in range(n) if k % 3 == 1] + [3 * (k + 1) for k in range(add_1, n // 3)]
        for i in range(1, n + 1):
            if d_list[i] % 2 == min_01:
                res_list[i - 1] = list_1.pop()
            else:
                res_list[i - 1] = list_2.pop()

    return " ".join([str(r) for r in res_list])


def main():
    n = int(input())
    ab_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, ab_list)
    print(res)


def test():
    # print(solve(5, [[1, 2], [1, 3], [3, 4], [3, 5]]))
    assert solve(5, [[1, 2], [1, 3], [3, 4], [3, 5]]) == "3 4 1 5 2"


if __name__ == "__main__":
    # test()
    main()

Submission status: Accepted

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

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


main()

Submission status: Accepted

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

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
group = [-1] * N
count = [0] * 2
stack = []
group[0] = 0
count[0] = 1
stack.append(0)
while stack:
    u = stack.pop()
    for v in G[u]:
        if group[v] == -1:
            group[v] = 1 - group[u]
            count[group[v]] += 1
            stack.append(v)
zeros = list(range(3, N+1, 3))
ones = list(range(1, N+1, 3))
twos = list(range(2, N+1, 3))
ans = [0] * N
for g in range(2):
    if count[g] <= N//3:
        for i in range(N):
            if group[i] == g:
                ans[i] = zeros.pop()
            else:
                if len(twos) > 0:
                    ans[i] = twos.pop()
                elif len(ones) > 0:
                    ans[i] = ones.pop()
                else:
                    ans[i] = zeros.pop()
        print(' '.join(map(str, ans)))
        exit()
for i in range(N):
    if group[i] == 0 and len(ones) > 0:
        ans[i] = ones.pop()
    elif group[i] == 1 and len(twos) > 0:
        ans[i] = twos.pop()
    else:
        ans[i] = zeros.pop()
print(' '.join(map(str, ans)))

Submission status: Accepted

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


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

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

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

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

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


print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    N=int(input())
    AB=[list(map(int, input().split())) for _ in range(N-1)]
    G=[[]for _ in range(N)]
    cnt=[0]*N
    for a,b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cnt[a-1]+=1
        cnt[b-1]+=1
    CI=sorted(((c,i) for i,c in enumerate(cnt)), reverse=True)
    ans=[0]*N
    C=[0]*N
    stack=[(0,-1,0)]
    while stack:
        u,p,d=stack.pop()
        for v in G[u]:
            if v!=p:
                stack.append((v,u,d^1))
                C[v]=d^1
    X=sum(C)
    if X<=N//3:
        D=[[i for i in range(1,N+1,3)]+[i for i in range(2,N+1,3)],[i for i in range(3,N+1,3)]]
        for i in range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[C[i]^1].pop()
    elif N-X<=N//3:
        D=[[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 range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[C[i]^1].pop()
    else:
        D=[[i for i in range(1,N+1,3)],[i for i in range(2,N+1,3)],[i for i in range(3,N+1,3)]]
        for i in range(N):
            if D[C[i]]:
                ans[i]=D[C[i]].pop()
            else:
                ans[i]=D[2].pop()
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	N = int(input())
	#1-Nの数を3で割った数の個数(あまり)
	a0 = int(N // 3)
	a1 = int((N + 2) // 3)
	a2 = int((N + 1) // 3)

	#グラフ構築
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#偶奇で判断 可能性判定	
	BF = BFS(G, 0, N)
	dist = BF.dist
	dis_even = 0
	dis_odd = 0
	for i in range(N):
		if dist[i] % 2 == 0:
			dis_even += 1
		else:
			dis_odd += 1

	ans = [0] * N
	judge = "No"
	S = [(i + 1) * 3 for i in range(a0)] + [i * 3 + 1 for i in range(a1)] + [i * 3 + 2 for i in range(a2)]
	if a2 <= dis_odd and a1 <= dis_even:
		judge = "Yes"
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a2:
					ans[i] = c1 * 3 + 2
					c1 += 1
			else:
				if c2 < a1:
					ans[i] = c2 * 3 + 1
					c2 += 1

		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1

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

	elif a1 <= dis_odd and a2 <= dis_even:
		judge = "Yes"
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a1:
					ans[i] = c1 * 3 + 2
					c1 += 1
			else:
				if c2 < a2:
					ans[i] = c2 * 3 + 1
					c2 += 1

		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1

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

	elif dis_odd <= a0:
		cnt = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				ans[i] = S[cnt]
				cnt += 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = S[cnt]
				cnt += 1

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

	else:
		cnt = 0
		for i in range(N):
			if dist[i] % 2 == 0:
				ans[i] = S[cnt]
				cnt += 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = S[cnt]
				cnt += 1

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

if __name__ == '__main__':
	main()