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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
G = [[] for i in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b-=1
  G[a].append(b)
  G[b].append(a)
ans = [0] * n
color = [[],[]]
def coloring(node,pre,oddeven):
  color[oddeven%2].append(node)
  for vi in G[node]:
    if vi != pre:
      coloring(vi,node,oddeven+1)
  return

coloring(0,-1,0)
A = n//3 + int(bool(n%3))
B = n//3 + int(n%3 == 2)
# この時点ではA>=Bである
if color[0] < color[1]:
  A,B = B,A
a=b=0; c=1
for i,ci in enumerate(color[0]):
  if i < A:
    ans[ci] = 3 * i + 1
  else:
    ans[ci] = 3 * c
    c += 1

for i,ci in enumerate(color[1]):
  if i < B:
    ans[ci] = 3 * i + 2
  else:
    ans[ci] = 3 * c
    c += 1
print(*ans)

Submission status: Runtime Error

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
  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: Runtime Error

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

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: Runtime Error

Solution code:
from collections import defaultdict, Counter, deque

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

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

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

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter, deque

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

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

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

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

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

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

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

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

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

Submission status: Runtime Error

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

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 n == 1 or n == 2:
    if m[n]:
      return m[n].pop()
    else:
      if m[0]:
        return m[0].pop()
      else:
        return m[3-n].pop()
  else:
    if m[n]:
      return m[n].pop()
    else:
      if m[1]:
        return m[1].pop()
      else:
        return m[2].pop()


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)
if sum(colors) > n - (n // 3):
  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: Runtime Error

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

m1 = deque([i for i in range(1, n + 1) if i % 3 == 1])
m2 = deque([i for i in range(1, n + 1) if i % 3 == 2])
m0 = deque([i for i in range(1, n + 1) if i % 3 == 0])

ans = [0] * n

if sum(colors) > n // 2:
  for itr, i in enumerate(colors):
    if i:
      if m1:
        ans[itr] = m1.pop()
      else:
        ans[itr] = m0.pop()
    else:
      if m2:
        ans[itr] = m2.pop()
      else:
        ans[itr] = m0.pop()
else:
  for itr, i in enumerate(colors):
    if not i:
      if m1:
        ans[itr] = m1.pop()
      else:
        ans[itr] = m0.pop()
    else:
      if m2:
        ans[itr] = m2.pop()
      else:
        ans[itr] = m0.pop()
print(*ans)

Submission status: Runtime Error

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

m1 = deque([i for i in range(1, n + 1) if i % 3 == 1])
m2 = deque([i for i in range(1, n + 1) if i % 3 == 2])
m0 = deque([i for i in range(1, n + 1) if i % 3 == 0])

ans = [0] * n

for itr, i in enumerate(colors):
  if i:
    if m1:
      ans[itr] = m1.pop()
    else:
      ans[itr] = m0.pop()
  else:
    if m2:
      ans[itr] = m2.pop()
    else:
      ans[itr] = m0.pop()

print(*ans)

Submission status: Runtime Error

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

color=[-1]*N
color[0]=0
next_i=[0]
visited=[0]*N
while next_i:
    i=next_i.pop()
    visited[i]=1
    while tree[i]:
        x=tree[i].pop()
        if visited[x]==0:
            next_i.append(x)
            color[x]=color[i]^1

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Runtime Error

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

color=[-1]*N
def coloring(n):
    if n==0:
        color[0]=0
    elif color[n]==-1:
        if n>0:
            coloring(n-1)
    if color[n]!=-1:
        while tree[n]:
            a=tree[n].pop()
            color[a]=color[n]^1
coloring(N-1)

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Runtime Error

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

color=[-1]*N
def coloring(n):
    if n==0:
        color[0]=0
    elif color[n]==-1:
        coloring(n-1)
    if color[n]!=-1:
        while tree[n]:
            a=tree[n].pop()
            color[a]=color[n]^1
coloring(N-1)

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Runtime Error

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

color=[-1]*N
def coloring(n):
    if n==0:
        color[0]=0
    elif color[n]==-1:
        coloring(n-1)
    else:
        while tree[n]:
            a=tree[n].pop()
            if color[a]==-1:
                color[a]=color[n]^1
coloring(N-1)

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Runtime Error

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

color=[-1]*N
def coloring(n):
    if n==0:
        color[0]=0
    elif color[n]==-1:
        coloring(n-1)
    while tree[n]:
        a=tree[n].pop()
        if color[a]==-1:
            color[a]=color[n]^1
coloring(N-1)

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
print(*ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

color=[-1]*N
def coloring(n):
    if n==0:
        color[0]=0
    if color[n]==-1:
        coloring(n-1)
    while tree[n]:
        a=tree[n].pop()
        color[a]=color[n]^1
try:
    coloring(N-1)
except IndexError:
    print('-1')
    exit()

n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

try:
    if n_blue>N/3 and n_red>N/3:
        for i in range(N):
            if color[i]==0 and mod1s:
                ans[i]=mod1s.pop()
            elif color[i]==1 and mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod3s.pop()
    elif n_red<=N/3:
        for i in range(N):
            if color[i]==1 and mod3s:
                ans[i]=mod3s.pop()
            else:
                if mod3s:
                    ans[i]=mod3s.pop()
                elif mod2s:
                    ans[i]=mod2s.pop()
                else:
                    ans[i]=mod1s.pop()
    else:
        for i in range(N):
            if color[i]==0 and mod3s:
                ans[i]=mod3s.pop()
            else:
                if mod3s:
                    ans[i]=mod3s.pop()
                elif mod2s:
                    ans[i]=mod2s.pop()
                else:
                    ans[i]=mod1s.pop()
    print(' '.join(map(str, ans)))
except IndexError:
    print('-1')

Submission status: Runtime Error

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

color=[-1]*N
def coloring(n):
    if n==0:
        color[0]=0
    if color[n]==-1:
        coloring(n-1)
    while tree[n]:
        a=tree[n].pop()
        color[a]=color[n]^1

coloring(N-1)
n_blue=N-sum(color)
n_red=sum(color)
mod1s=[i+1 for i in range(0,N,3)]
mod2s=[i+1 for i in range(1,N,3)]
mod3s=[i+1 for i in range(2,N,3)]
ans=[0]*N

if n_blue>N/3 and n_red>N/3:
    for i in range(N):
        if color[i]==0 and mod1s:
            ans[i]=mod1s.pop()
        elif color[i]==1 and mod2s:
            ans[i]=mod2s.pop()
        else:
            ans[i]=mod3s.pop()
elif n_red<=N/3:
    for i in range(N):
        if color[i]==1 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()
else:
    for i in range(N):
        if color[i]==0 and mod3s:
            ans[i]=mod3s.pop()
        else:
            if mod3s:
                ans[i]=mod3s.pop()
            elif mod2s:
                ans[i]=mod2s.pop()
            else:
                ans[i]=mod1s.pop()

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

Submission status: Runtime Error

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

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

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

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

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

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

tree(0)

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

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

print(*ans)

Submission status: Runtime Error

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

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

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

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

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

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

tree(0)

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

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

print(*ans)

Submission status: Runtime Error

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

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

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

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

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

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

tree(0)

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

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

print(*ans)

Submission status: Runtime Error

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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

bp = [-1] * N
stack = [(0, None, 0)]
while stack:
    v, p, b = stack.pop()
    bp[v] = b
    b += 1
    b &= 1
    for u in graph[v]:
        if u == p:
            continue
        stack.append((u, v, b))

cnt0 = N // 3
cnt1 = (N + 2) // 3
cnt2 = (N + 1) // 3
vs0 = [i for i, b in enumerate(bp) if b == 0]
vs1 = [i for i, b in enumerate(bp) if b == 1]
ans_mod3 = [-1] * N
if bp.count(0) <= N // 3:
    for i in range(cnt0):
        ans_mod3[vs0.pop()] = 0
    cnt0 = 0
elif bp.count(1) <= N // 3:
    for i in range(cnt0):
        ans_mod3[vs1.pop()] = 0
    cnt0 = 0
else:
    for i in range(cnt1):
        ans_mod3[vs0.pop()] = 1
    cnt1 = 0
    for i in range(cnt2):
        ans_mod3[vs1.pop()] = 2
    cnt2 = 0

for _ in range(cnt0):
    if vs0:
        ans_mod3[vs0.pop()] = 0
    elif vs1:
        ans_mod3[vs1.pop()] = 0
for _ in range(cnt1):
    if vs0:
        ans_mod3[vs0.pop()] = 1
    elif vs1:
        ans_mod3[vs1.pop()] = 1
for _ in range(cnt2):
    if vs0:
        ans_mod3[vs0.pop()] = 2
    elif vs1:
        ans_mod3[vs1.pop()] = 2

st = [3, 1, 2]
ans = []
for a in ans_mod3:
    ans.append(st[a])
    st[a] += 3
print(*ans)