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:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    AB = [[] for j in range(N)]

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

    ans = [0] * N
    S = collections.deque()
    S.append([0, 0])
    v = set()
    v.add(0)
    while S:
        c = S.pop()
        ans[c[0]] = c[1] % 2
        for next in AB[c[0]]:
            if next not in v:
                v.add(next)
                S.append([next, c[1] + 1])

    bcnt = sum(ans)
    q, r = divmod(N, 3)
    onenum = q
    twonum = q + N % 3
    if r == 1:
        onenum += 1
    elif r == 2:
        onenum += 1
        twonum += 1
    thrnum = q

    onecnt = 0
    twocnt = 0
    thrcnt = 0
    for a in ans:
        if a == 0:
            if onenum > 0:
                onenum -= 1
                print(onecnt * 3 + 1, end=" ")
                onecnt += 1
            else:
                thrcnt += 1
                print(thrcnt * 3, end=" ")
        else:
            if twonum > 0:
                twonum -= 1
                print(twocnt * 3 + 2, end=" ")
                twocnt += 1
            else:
                thrcnt += 1
                print(thrcnt * 3, end=" ")






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():

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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():

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

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

    # start point of BFS

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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

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


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

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

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

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

Submission status: Wrong Answer

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


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

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


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

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
N = int(input())

g = defaultdict(list)
for i in range(N-1):
    a, b = map(int,input().split())
    if b < a:
        a,b = b,a
    g[a].append(b)

AB = [0]*(N+1)
l = [1]
mark = 1
while l:
    nl = []
    for v in l:
        AB[v] = mark
        nl.extend(g[v])
    mark *= -1
    l = nl
cnt = Counter(AB)
NA = cnt[1]
NB = cnt[-1]

N0 = [3*i for i in range(1,(N+3)//3)]
N1 = [3*i+1 for i in range((N+2)//3)]
N2 = [3*i+2 for i in range((N+1)//3)]

ans = [0]*(N+1)
if NA <= len(N0):
    N12 = N1+N2
    for i in range(1,N+1):
        if AB[i] == 1:
            ans[i] = N0.pop()
        else:
            if N12:
                ans[i] = N12.pop()
            else:
                ans[i] = N0.pop()
elif NB <= len(N0):
    N12 = N1+N2
    for i in range(1,N+1):
        if AB[i] == -1:
            ans[i] = N0.pop()
        else:
            if N12:
                ans[i] = N12.pop()
            else:
                ans[i] = N0.pop()
else:
    for i in range(1,N+1):
        if AB[i] == 1:
            if N1:
                ans[i] = N1.pop()
            else:
                ans[i] = N0.pop()
        else:
            if N2:
                ans[i] = N2.pop()
            else:
                ans[i] = N0.pop()
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
connection = [[] for _ in range(N+1)]
distance3 = [[] for _ in range(N+1)]
remain = [i for i in range(1,N+1)]
Nesessary = [False for _ in range(N+1)]

for node in ab:
    connection[node[0]].append(node[1])
    connection[node[1]].append(node[0])

conne_num = [[i+1, 0] for i in range(N)]

p = 0
for conne in connection[1:]:
    p += 1
    for current1 in conne:
        for current2 in connection[current1]:
            for current3 in connection[current2]:
                if current3 not in conne:
                    distance3[p].append(current3)
                    conne_num[p-1][1] += 1
                    Nesessary[p] = True

conne_num = sorted(conne_num, key=lambda x:int(x[1]), reverse =True)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(b)
  
colors = [-1] * n

# ２色で塗分けする。
q = deque()
# 現在見ている頂点、親の色
q.append((0, 0))
while q:
  v, pcol = q.popleft()
  # 親と異なる色で塗る。
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
    for i in e[v]:
      if colors[i] == -1:
        q.append((i, col))

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

# print(m)

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

ans = [0] * n

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

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[0] <= n // 3:
   odd, even = even, odd
if num[1] <= n // 3:
    r = r2 + r1 + r0
else:
    r = r2 + r0 + r1
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

Submission status: Wrong Answer

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

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

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

print(*ans)

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[0] <= (n + 1) // 3:
   odd, even = even, odd
if num[1] <= (n + 1) // 3:
    r = r2 + r1 + r0
else:
    r = r2 + r0 + r1
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[0] <= (n + 2) // 3:
   odd, even = even, odd
if num[1] <= (n + 2) // 3:
    r = r2 + r1 + r0
else:
    r = r2 + r0 + r1
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

Submission status: Wrong Answer

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

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

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

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(a)
  
colors = [-1] * n

# ２色で塗分けする。
q = deque()
# 現在見ている頂点、親の色
q.append((0, 0))
while q:
  v, pcol = q.popleft()
  # 親と異なる色で塗る。
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
  else:
    col = colors[v]
  for i in e[v]:
    if colors[i] == -1:
      q.append((i, col))

if -1 in colors:
  raise ValueError("error!")

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

# print(m)

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

ans = [0] * n

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

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[0] <= n / 3:
   odd, even = even, odd
if num[1] <= n / 3:
    r = r2 + r1 + r0
else:
    r = r2 + r0 + r1
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[0] <= n / 3:
   odd, even = even, odd
if num[0] > n / 3 and num[0] > n / 3:
    r = r2 + r0 + r1
else:
    r = r2 + r1 + r0
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(a)
  
colors = [-1] * n

# ２色で塗分けする。
q = deque()
# 現在見ている頂点、親の色
q.append((0, 0))
while q:
  v, pcol = q.popleft()
  # 親と異なる色で塗る。
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
  else:
    col = colors[v]
  for i in e[v]:
    if colors[i] == -1:
      q.append((i, col))

if -1 in colors:
  raise ValueError("error!")

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

# print(m)

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

ans = [0] * n

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

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[0] <= n / 3:
   odd, even = even, odd
if num[0] > n / 3 and num[0] > n / 3:
    r = r2 + r0 + r1
else:
    r = r2 + r1 + r0
ans = [0] * n
for i in even:
    ans[i] = r.pop()
for i in odd:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

Submission status: Wrong Answer

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

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
num = [1, 0]
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
            num[d%2] += 1
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if num[1] <= n / 3:
   odd, even = even, odd
if num[0] > n / 3 and num[0] > n / 3:
    r = r2 + r1 + r0
else:
    r = r2 + r0 + r1
ans = [0] * n
for i in even:
    ans[i] = r.pop()
for i in odd:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def bfs(n,g):
    dis = [-1 for _ in range(n)]
    que = deque([])
    que.append(0)
    dis[0] = 0
    ODD = []
    EVEN = [0]
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] != -1:
                continue
            dis[g[go][i]] = dis[go] + 1
            if dis[g[go][i]]%2 == 0:
                EVEN.append(g[go][i])
            else:
                ODD.append(g[go][i])
            que.append(g[go][i])
    return EVEN,ODD

def main():
    n = inp()
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = inpm()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    EVEN,ODD = bfs(n,g)
    ans = [0 for _ in range(n)]
    check = [1 for _ in range(n)]
    if len(ODD) <= n//3:
        x = 1
        while ODD:
            index = ODD.pop()
            ans[index] = 3*x
            check[3*x-1] = 0
            x += 1
        i = 0
        while EVEN:
            index = EVEN.pop()
            while not check[i]:
                i += 1
            ans[index] = check[i]
            i += 1
        print(*ans)
        return
    if len(EVEN) <= n//3:
        x = 1
        while EVEN:
            index = EVEN.pop()
            ans[index] = 3*x
            check[3*x-1] = 0
            x += 1
        i = 0
        while ODD:
            index = ODD.pop()
            while not check[i]:
                i += 1
            ans[index] = check[i]
            i += 1
        print(*ans)
        return
    mod0 = deque()
    mod1 = deque()
    mod2 = deque()
    for i in range(1,n+1):
        if i%3 == 0:
            mod0.append(i)
        if i%3 == 1:
            mod1.append(i)
        if i%3 == 2:
            mod2.append(i)
    if len(ODD) <= len(EVEN):
        while mod1:
            index = EVEN.pop()
            ans[index] = mod1.pop()
        while mod2:
            index = ODD.pop()
            ans[index] = mod2.pop()
    else:
        while mod1:
            index = ODD.pop()
            ans[index] = mod1.pop()
        while mod2:
            index = EVEN.pop()
            ans[index] = mod2.pop()
    while mod0:
        if EVEN:
            index = EVEN.pop()
        else:
            index = ODD.pop()
        ans[index] = mod0.pop()
    print(*ans)

if __name__ == "__main__":
    main()