Problem p02749 (python)

Fixed submission:
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
 
group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)
 
three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))

Buggy submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(2147483647)

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


vertice = [-1 for _ in range(n)]
stack = [(0, 0)]

while stack:
    parent, vertex = stack.pop()
    vertice[vertex] = vertice[parent] * (-1)
    for next in edges[vertex]:
        if next != parent:
            stack.append((vertex, next))

# vertice = [0 for _ in range(n)]
#
#
# def dfs(v, color_i):
#     vertice[v] = color_i
#     for i in edges[v]:
#         if vertice[i] == 0:
#             dfs(i, color_i*(-1))
#
# dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            elif not3:
                ans.append(str(not3.pop()))
        else:
            ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            elif not3:
                ans.append(str(not3.pop()))
        else:
            ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(2147483647)

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


vertice = [-1 for _ in range(n)]
stack = [(0, 0)]

while stack:
    parent, vertex = stack.pop()
    vertice[vertex] = vertice[parent] * (-1)
    for next in edges[vertex]:
        if next != parent:
            stack.append((vertex, next))

# vertice = [0 for _ in range(n)]
#
#
# def dfs(v, color_i):
#     vertice[v] = color_i
#     for i in edges[v]:
#         if vertice[i] == 0:
#             dfs(i, color_i*(-1))
#
# dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(not3.pop()))
        else:
            ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    if v == -1:
        if num3:
            ans.append(str(num3.pop()))
        else:
            ans.append(str(not3.pop()))
    else:
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(2147483647)

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


vertice = [-1 for _ in range(n)]
stack = [(0, 0)]

while stack:
    parent, vertex = stack.pop()
    vertice[vertex] = vertice[parent] * (-1)
    for next in edges[vertex]:
        if next != parent:
            stack.append((vertex, next))

# vertice = [0 for _ in range(n)]
#
#
# def dfs(v, color_i):
#     vertice[v] = color_i
#     for i in edges[v]:
#         if vertice[i] == 0:
#             dfs(i, color_i*(-1))
#
# dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2147483647)

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


vertice = [0 for _ in range(n)]


def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

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


vertice = [0 for _ in range(n)]


def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

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


vertice = [0 for _ in range(n)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**10)

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


vertice = [0 for _ in range(n)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
  a, b = map(int, input().split())
  edges[a - 1].append(b - 1)
  edges[b - 1].append(a - 1)


vertice = [0 for _ in range(n)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, n+1) if i % 3 != 0]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, n+1) if i % 3 == 1]
    num2 = [i for i in range(1, n+1) if i % 3 == 2]
    num3 = [i for i in range(1, n+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
  a, b = map(int, input().split())
  edges[a - 1].append(b - 1)
  edges[b - 1].append(a - 1)


vertice = [0 for _ in range(n)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, N+1) if i % 3 == 1]
    num2 = [i for i in range(1, N+1) if i % 3 == 2]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
from collections import Counter
import sys
sys.setrecursionlimit(1000000000)

N = int(input())

edges = {i:[] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

vertice = [0 for _ in range(N+1)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(1, 1)

c = Counter(vertice)
ans = []
if c[1] > N/3 and c[2] > N/3:
    nums1 = [i for i in range(1, N+1) if i % 3 == 1]
    nums2 = [i for i in range(1, N+1) if i % 3 == 2]
    nums3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))
elif c[1] <= N/3:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))
else:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))

print(" ".join(ans))

Buggy submission (verdict: Runtime Error):
from collections import Counter
import sys
sys.setrecursionlimit(1000000000)

N = int(input())

edges = {i:[] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

vertice = [0 for _ in range(N+1)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(1, 1)

c = Counter(vertice)
ans = []
if c[1] > N/3 and c[2] > N/3:
    nums1 = [i for i in range(1, N+1) if i % 3 == 1]
    nums2 = [i for i in range(1, N+1) if i % 3 == 2]
    nums3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))
elif c[1] <= N/3:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))
else:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))

print("".join(ans))

Buggy submission (verdict: Runtime Error):
from collections import Counter

N = int(input())

edges = {i:[] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

vertice = [0 for _ in range(N+1)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(1, 1)

c = Counter(vertice)
ans = []
if c[1] > N/3 and c[2] > N/3:
    nums1 = [i for i in range(1, N+1) if i % 3 == 1]
    nums2 = [i for i in range(1, N+1) if i % 3 == 2]
    nums3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))
elif c[1] <= N/3:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))
else:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))

print("".join(ans))