Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.

Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

2\leq N\leq 2\times 10^5

1\leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

If no permutation satisfies the condition, print -1.

Otherwise, print a permutation satisfying the condition, with space in between.
If there are multiple solutions, you can print any of them.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

1 2 5 4 3 

The distance between two vertices is 3 for the two pairs (2, 4) and (2, 5).

p_2 + p_4 = 6

p_2\times p_5 = 6

Thus, this permutation satisfies the condition.



Sample input:
5
1 2
1 3
3 4
3 5


Sample output:
1 2 5 4 3

Submission status: Wrong Answer

Solution code:

"""
Writer:SPD_9X2

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

mod3で、
赤/青
10/20
20/10
12/0
0/12
の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 dis[i] % 2 != 0:
        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 = [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 dis[i] % 2 != 1:
        nex = use[2]
        use[2] += 3

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

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



print (-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
T = [deque() for _ in range(N+1)]
seen = [False]*(N+1)
a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
T[a].append(b)
seen[a] = True
seen[b] = True
for _ in range(N-2):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  if not seen[a]:
    T[b].append(a)
  else:
    T[a].append(b)
  seen[a] = True
  seen[b] = True
q = deque([[1, 0]])
even = deque()
odd = deque()
dist = 0
while q:
  cur, dist = q.pop()
  if dist % 2 == 0:
    even.append(cur)
  else:
    odd.append(cur)
  for c in T[cur]:
    q.append([c, dist+1])
if len(even) < 1 or len(odd) < 1:
  print(-1)
else:
  ans = [0]*(N+1)
  threes = deque(list(range(3, N+1, 3)))
  if len(even) > N//3 and len(odd) > N//3:
    i = 0
    while even and 3*i+1 <= N:
      e = even.pop()
      ans[e] = 3*i+1
      i += 1
    if even:
      while even:
        e = even.pop()
        thr = threes.pop()
        ans[e] = thr
    i = 0
    while odd and 3*i+2 <= N:
      o = odd.pop()
      ans[o] = 3*i+2
      i += 1
    if odd:
      while odd:
        o = odd.pop()
        thr = threes.pop()
        ans[o] = thr
  elif len(even) <= N//3:
    while even and threes:
      e = even.pop()
      thr = threes.pop()
      ans[e] = thr
    while odd and threes:
      o = odd.pop()
      thr = threes.pop()
      ans[o] = thr
    i = 0
    while odd and i*3+1 <= N:
      o = odd.pop()
      ans[o] = i * 3 +1
      i += 1
    i = 0
    while odd and i*3+2 <= N:
      o = odd.pop()
      ans[o] = i * 3 + 2
      i += 1
  else:
    while odd and threes:
      e = odd.pop()
      thr = threes.pop()
      ans[e] = thr
    while even and threes:
      o = even.pop()
      thr = threes.pop()
      ans[o] = thr
    i = 0
    while even and i*3+1 <= N:
      o = even.pop()
      ans[o] = i * 3 +1
      i += 1
    i = 0
    while even and i*3+2 <= N:
      o = even.pop()
      ans[o] = i * 3 + 2
      i += 1
  print(" ".join([str(a) for a in ans[1:]]))

Submission status: Wrong Answer

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(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: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

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

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for i in range(1, N + 1):
    if i % 3 == 0:
        mod0.append(i)
    elif i % 3 == 1:
        mod1.append(i)
    else:
        mod2.append(i)

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


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N // 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N // 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

# for i in range(1, N + 1):
    # modfit(i)

print()

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
tree = [[0, 0] for _ in range(N+1)] # [parent, depth(e or o)]
edge = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

queue = deque([1])
d, even_or_odd = 1, [1, 0]
while len(queue) > 0:
    newq = set()
    for _ in range(len(queue)):
        p = queue.pop()
        for q in edge[p]:
            if q != tree[p][0]:
                newq.add(q)
                tree[q][0], tree[q][1] = p, d % 2
    even_or_odd[d % 2] += len(newq)
    d += 1
    queue = deque(list(newq))

stock = [N//3] * 3
for i in range(N%3):    stock[i] += 1

if min(even_or_odd) > N//3:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0 and i <= stock[0] - 1:
            ans.append(3*i + 1)
            i += 1
        elif tree[l][1] != 0 and j <= stock[1] - 1:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
elif even_or_odd[0] <= stock[0] - 1:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0:
            ans.append(3*k)
            k += 1
        elif i <= stock[0] - 1:
            ans.append(3*i + 1)
            i += 1
        elif j <= stock[1] - 1:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
else:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] != 0:
            ans.append(3*k)
            k += 1
        elif i <= stock[0] - 1:
            ans.append(3*i + 1)
            i += 1
        elif j <= stock[1] - 1:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
T = [deque() for _ in range(N+1)]
seen = [False]*(N+1)
a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
T[a].append(b)
seen[a] = True
seen[b] = True
for _ in range(N-2):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  if not seen[a]:
    T[b].append(a)
  else:
    T[a].append(b)
  seen[a] = True
  seen[b] = True
q = deque([[1, 0]])
even = deque()
odd = deque()
dist = 0
while q:
  cur, dist = q.pop()
  if dist % 2 == 0:
    even.append(cur)
  else:
    odd.append(cur)
  for c in T[cur]:
    q.append([c, dist+1])
if len(even) < 1 or len(odd) < 1:
  print(-1)
else:
  ans = [0]*(N+1)
  threes = deque(list(range(3, N+1, 3)))
  if len(even) > N//3 and len(odd) > N//3:
    i = 0
    while even and 3*i+1 <= N:
      e = even.pop()
      ans[e] = 3*i+1
      i += 1
    if even:
      while even:
        e = even.pop()
        thr = threes.pop()
        ans[e] = thr
    i = 0
    while odd and 3*i+2 <= N:
      o = odd.pop()
      ans[o] = 3*i+2
      i += 1
    if odd:
      while even:
        o = odd.pop()
        thr = threes.pop()
        ans[o] = thr
  elif len(even) <= N//3:
    while even and threes:
      e = even.pop()
      thr = threes.pop()
      ans[e] = thr
    while odd and threes:
      o = odd.pop()
      thr = threes.pop()
      ans[o] = thr
    i = 0
    while odd and i*3+1 <= N:
      o = odd.pop()
      ans[o] = i * 3 +1
      i += 1
    i = 0
    while odd and i*3+2 <= N:
      o = odd.pop()
      ans[o] = i * 3 + 2
      i += 1
  else:
    while odd and threes:
      e = odd.pop()
      thr = threes.pop()
      ans[e] = thr
    while even and threes:
      o = even.pop()
      thr = threes.pop()
      ans[o] = thr
    i = 0
    while even and i*3+1 <= N:
      o = even.pop()
      ans[o] = i * 3 +1
      i += 1
    i = 0
    while even and i*3+2 <= N:
      o = even.pop()
      ans[o] = i * 3 + 2
      i += 1
  print(" ".join([str(a) for a in ans[1:]]))

Submission status: Wrong Answer

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_red = 0
count_blue = 0
for i in range(1,len(dist)):
    if dist[i] % 2 == 0:
        count_red += 1
    else:
        count_blue += 1
#場合分け
if count_red > n/3 and count_blue > 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_red <= n/3:
    #1からの距離が偶数のところが全体の1/3を閉めない場合
    #そこに全部3の倍数を入れてしまえば、題意を満たす
    li = rem_1 + rem_2
    index = 0
    ans = []
    for i in range(1,len(dist)):
        if dist[i] % 2 == 0:
            ans.append(rem_0[index_0])
        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
    ans = []
    for i in range(1,len(dist)):
        if dist[i] % 2 == 1:
            ans.append(rem_0[index_0])
        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: Wrong Answer

Solution code:
from collections import deque

N = int(input())
tree = [[0, 0] for _ in range(N+1)] # [parent, depth(e or o)]
edge = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

queue = deque([1])
d, even_or_odd = 1, [1, 0]
while len(queue) > 0:
    newq = set()
    for _ in range(len(queue)):
        p = queue.pop()
        for q in edge[p]:
            if q != tree[p][0]:
                newq.add(q)
                tree[q][0], tree[q][1] = p, d % 2
    even_or_odd[d % 2] += len(newq)
    d += 1
    queue = deque(list(newq))

stock = [N//3] * 3
for i in range(N%3):    stock[i] += 1

if min(even_or_odd) > N//3:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0 and i <= stock[0] - 1:
            ans.append(3*i + 1)
            i += 1
        elif tree[l][1] != 0 and j <= stock[1] - 1:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
elif even_or_odd[0] <= stock[0] - 1:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0:
            ans.append(3*k)
            k += 1
        elif i <= N//3:
            ans.append(3*i + 1)
            i += 1
        elif j <= N//3:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
else:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] != 0:
            ans.append(3*k)
            k += 1
        elif i <= N//3:
            ans.append(3*i + 1)
            i += 1
        elif j <= N//3:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

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

Solution code:
from collections import deque
import random
isdebug=0
if isdebug==0:
    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)
else:
    N=20*10**4
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=random.randrange(i+1),i+1
        G[a].append(b)
        G[b].append(a)
dist=[-1 for i in range(N)]
X=[]
Y=[]
q=deque([0])
dist[0]=0
while(len(q)>0):
    r=q.popleft()
    if dist[r]%2==0:
        X.append(r)
    else:
        Y.append(r)
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=dist[r]+1
            q.append(p)
P=[0 for i in range(N)]
que=deque([])
if min(len(X),len(Y))<=N//3:
    for i in range(N):
        if i%3==0:
            que.appendleft(i)
        else:
            que.append(i)
    if len(X)<len(Y):
        for i in X:
            t=que.popleft()
            P[i]=t+1
        for i in Y:
            t=que.pop()
            P[i]=t+1
    else:
        for i in Y:
            t=que.popleft()
            P[i]=t+1
        for i in X:
            t=que.pop()
            P[i]=t+1
else:
    for i in range(N):
        if i%3==0:
            que.appendleft(i)
    for i in range(N):
        if i%3==1:
            que.appendleft(i)
        elif i%3==2:
            que.append(i)
    for i in X:
        t=que.popleft()
        P[i]=t+1
    for i in Y:
        t=que.pop()
        P[i]=t+1
print(*P)

Submission status: Wrong Answer

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 i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    ans[i] = nums[i].pop()
                    break

if cnts[0] <= n // 3:
    solve(0)
elif cnts[1] <= n // 3:
    solve(1)
else:
    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: Wrong Answer

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

Submission status: Wrong Answer

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 i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    ans[i] = nums[i].pop()
                    break

if cnts[0] <= n // 3:
    solve(0)
elif cnts[1] <= n // 3:
    solve(1)
elif cnts[0] > n // 3 and cnts[1] > n // 3:
    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()
else:
    print(-1)
    exit()

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def dfs(n, d):
    if depth[n] != -1:
        return
    depth[n] = d
    for nn in eAB[n]:
        dfs(nn, d + 1)
    return


N = int(input())
AB = [inpl() for i in range(N - 1)]

eAB = [[] for i in range(N)]
for a, b in AB:
    eAB[a - 1].append(b - 1)
    eAB[b - 1].append(a - 1)

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

dfs(0, 0)

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

ans = [-1 for i in range(N)]
if len(eo[0]) > N // 3 and len(eo[1]) > N // 3:
    for i in range(N // 3):
        ans[3 * i] = eo[0][i]
        ans[3 * i + 1] = eo[1][i]
    t_0 = N // 3
    t_1 = N // 3
elif len(eo[0]) <= N // 3:
    for i in range(len(eo[0])):
        ans[3 * i + 2] = eo[0][i]
    t_0 = len(eo[0])
    t_1 = 0
elif len(eo[1]) <= N // 3:
    for i in range(len(eo[1])):
        ans[3 * i + 2] = eo[1][i]
    t_0 = 0
    t_1 = len(eo[1])

# print(eo, t_0, t_1)
for i in range(N):
    if ans[i] != -1:
        continue
    if t_0 < len(eo[0]):
        ans[i] = eo[0][t_0]
        t_0 += 1
    else:
        ans[i] = eo[1][t_1]
        t_1 += 1
# print(ans)
print(" ".join(list(map(str, [a + 1 for a in ans]))))

Submission status: Wrong Answer

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(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:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        f = 1
        break
  else:
    if len(nm[2]):
      res[i] = nm[2].pop()
    else:
      if len(nm[0]):
        res[i] = nm[0].pop()
      else:
        f = 1
        break
if f:
  nm = [[] for _ in range(3)]
  for i in range(1, N + 1): nm[i % 3].append(i)
  res = [0] * (N + 1)
  for i in range(1, N + 1):
    if cl[i] == 0:
      if len(nm[1]):
        res[i] = nm[1].pop()
      else:
        if len(nm[0]):
          res[i] = nm[0].pop()
        else:
          print(-1)
          exit(0)
    else:
      if len(nm[2]):
        res[i] = nm[2].pop()
      else:
        if len(nm[0]):
          res[i] = nm[0].pop()
        else:
          print(-1)
          exit(0)
print(*res[1: ])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
tree = [[0, 0] for _ in range(N+1)] # [parent, depth(e or o)]
edge = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

queue = deque([1])
d, even_or_odd = 1, [1, 0]
while len(queue) > 0:
    newq = set()
    for _ in range(len(queue)):
        p = queue.pop()
        for q in edge[p]:
            if q != tree[p][0]:
                newq.add(q)
                tree[q][0], tree[q][1] = p, d % 2
    even_or_odd[d % 2] += len(newq)
    d += 1
    queue = deque(list(newq))


if min(even_or_odd) > N//3:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0 and i <= N//3:
            ans.append(3*i + 1)
            i += 1
        elif tree[l][1] != 0 and j <= N//3:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
elif even_or_odd[0] <= N//3:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0:
            ans.append(3*k)
            k += 1
        elif i <= N//3:
            ans.append(3*i + 1)
            i += 1
        elif j <= N//3:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
else:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] != 0:
            ans.append(3*k)
            k += 1
        elif i <= N//3:
            ans.append(3*i + 1)
            i += 1
        elif j <= N//3:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
print(' '.join(map(str, ans)))