Problem p02850 (python)

Fixed submission:
import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = 1
colors = {}
ends = {}
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    ng = {}
    global palette
    if parent > 0:
        ng[colors[parent]] = True
    for edge in edges[root]:
        if edge in colors:
            color = colors[edge]
        elif palette - len(ng) > 0:
            color = 1
            while color in ng:
                color += 1
            colors[edge] = color
        else:
            palette += 1
            color = palette
            colors[edge] = color

        ng[color] = True
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(palette)
for edge in range(1,N):
    print(colors[edge])

Buggy submission (verdict: Runtime Error):
N = int(input())
palette = [1]
colors = [None] * N
ends = [None] * N
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

for edge in range(1,N):
    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    current_palette = palette[:]
    if parent > 0:
        del current_palette[current_palette.index(colors[parent])]
    for edge in edges[root]:
        if edge == parent:
            continue
        if len(current_palette) > 0:
            colors[edge] = current_palette[0]
            del current_palette[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[edge] = color
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

color_edges(0, 1)

print(len(palette))
for edge in range(1,N):
    print(colors[edge])

Buggy submission (verdict: Runtime Error):
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)


def color_edges(parent, root):
    p = palette[:]
    if parent > 0:
        p = [color for color in p if color != colors[parent]]
    for i in ends[root]:
        if i == parent:
            continue
        if len(p) > 0:
            colors[i] = p[0]
            del p[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[i] = color
    for i in ends[root]:
        if i == parent:
            continue
        a, b = edges[i]
        if a == root:
            color_edges(i, b)
        else:
            color_edges(i, a)

color_edges(0, 1)

print(len(palette))
for i in range(1,N):
    print(colors[i])

Buggy submission (verdict: Runtime Error):
N = int(input())
palette = [1]
colors = [None] * N
edges = [None] * N
ends = {}

for i in range(1,N):
    edges[i] = [int(n) for n in input().split()]

for i in range(1,N):
    a, b = edges[i]
    if a not in ends:
        ends[a] = [i]
    else:
        ends[a].append(i)
    if b not in ends:
        ends[b] = [i]
    else:
        ends[b].append(i)

order = []
_ends = ends.copy()
while len(_ends) > 0:
    leafs = [leaf for leaf in _ends if len(_ends[leaf]) == 1]
    for leaf in leafs:
        if leaf not in _ends:
            continue
        order.insert(0, leaf)
        edge = _ends[leaf][0]
        a, b = edges[edge]
        if a == leaf:
            parent = b
        else:
            parent = a
        _ends[parent] = [e for e in _ends[parent] if e != edge]
        del _ends[leaf]
        if len(_ends[parent]) == 0:
            order.insert(0,parent)
            del(_ends[parent])

root = [node for node in ends if len(ends[node]) > 1][0]

def color_edges(parent, root):
    p = palette[:]
    if parent > 0:
        p = [color for color in p if color != colors[parent]]
    for i in ends[root]:
        if i == parent:
            continue
        if len(p) > 0:
            colors[i] = p[0]
            del p[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[i] = color
        a, b = edges[i]
        if a == root:
            color_edges(i, b)
        else:
            color_edges(i, a)

"""
for i in order:
    p = palette[:]
    for j in ends[i]:
        if colors[j]:
            p = [color for color in p if color != colors[j]]
        else:
            if len(p) > 0:
                colors[j] = p[0]
                del p[0]
            else:
                color = len(palette) + 1
                palette.append(color)
                colors[j] = color
"""

color_edges(0, root)

print(len(palette))
for i in range(1,N):
    print(colors[i])