Problem p02850 (python)

Fixed submission:
from collections import deque

N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)

# [print(i, t) for i, t in enumerate(tree)]


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    edge_colors = dict()
    node_colors = [0] * len(tree)
    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        parent_color = node_colors[q]

        cnt = 1
        for v in tree[q]:
            if not seen[v]:
                if cnt == parent_color:
                    cnt += 1

                edge_colors[(q, v)] = cnt
                node_colors[v] = cnt
                queue.append(v)
                cnt += 1



    """
    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = residual.pop()
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)
    """

    return edge_colors


edge_colors = bfs(tree, 0)

print(max([c for key, c in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]
# print(edge_colors)

# show_tree(tree)

Buggy submission (verdict: Runtime Error):
from collections import OrderedDict
# import matplotlib.pyplot as plt
# import networkx as nx

def get_key(p, q):
    v, w = min(p, q), max(p, q)
    return str(v) + "to" + str(w)


def get_color_set(g, key):
    colorset = set()
    fromkey = key.split("to")[0]
    for k, v in g.items():
        if fromkey in k:
            colorset.add(v)

    return colorset


def show_tree(tree, edge_labels):
    graph = nx.Graph()
    labels = {}
    for i, s in enumerate(tree):
        for d in s:
            # graph.node(str(s))
            # graph.node(str(d))
            graph.add_edge(i, d)
            labels[(i, d)] = edge_labels[get_key(i, d)]

    pos = nx.spring_layout(graph)
    # print(graph)
    nx.draw_networkx(graph, pos=pos)
    nx.draw_networkx_edge_labels(graph, pos, labels)
    # nx.draw_networkx_edge_labels(graph, pos)
    plt.show()



N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]
g = OrderedDict()

ans = OrderedDict()
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    g[in1] = set()
    g[in2] = set()

    ans[get_key(in1, in2)] = 0


# [print(i, t) for i, t in enumerate(tree)]

edge_colors = OrderedDict()


def dfs(tree, p, seen, g, color, all_color_set):
    if p >= len(tree):
        return

    if seen[p]:
        return

    seen[p] = True
    # print(p)

    for q in range(len(tree[p])):
        f = p   # from
        d = tree[p][q]  # dist

        key = get_key(f, d)

        if key not in edge_colors.keys():
            this_color_set = g[f] | g[d]
            cand_colors = all_color_set - this_color_set
            if len(cand_colors) > 0:
                g[d].add(min(cand_colors))
                edge_colors[key] = min(cand_colors)
            else:
                edge_colors[key] = color
                g[d].add(color)
                all_color_set.add(color)
                g[p] = g[p] | g[tree[p][q]]
                color += 1

        dfs(tree, tree[p][q], seen, g, color, all_color_set)


seen = [False] * N
all_color_set = set()
dfs(tree, 0, seen, g, 1, all_color_set)

ans = [edge_colors[k] for k in ans.keys()]

print(max(ans))
[print(a) for a in ans]

# [print(k, v) for k, v in edge_colors.items()]

# show_tree(tree, edge_colors)

Buggy submission (verdict: Runtime Error):
from collections import OrderedDict
import matplotlib.pyplot as plt
import networkx as nx

def get_key(p, q):
    v, w = min(p, q), max(p, q)
    return str(v) + "to" + str(w)


def get_color_set(g, key):
    colorset = set()
    fromkey = key.split("to")[0]
    for k, v in g.items():
        if fromkey in k:
            colorset.add(v)

    return colorset


def show_tree(tree, edge_labels):
    graph = nx.Graph()
    labels = {}
    for i, s in enumerate(tree):
        for d in s:
            # graph.node(str(s))
            # graph.node(str(d))
            graph.add_edge(i, d)
            labels[(i, d)] = edge_labels[get_key(i, d)]

    pos = nx.spring_layout(graph)
    # print(graph)
    nx.draw_networkx(graph, pos=pos)
    nx.draw_networkx_edge_labels(graph, pos, labels)
    # nx.draw_networkx_edge_labels(graph, pos)
    plt.show()



N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]
g = OrderedDict()

ans = OrderedDict()
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    g[in1] = set()
    g[in2] = set()

    ans[get_key(in1, in2)] = 0


# [print(i, t) for i, t in enumerate(tree)]

edge_colors = OrderedDict()


def dfs(tree, p, seen, g, color, all_color_set):
    if p >= len(tree):
        return

    if seen[p]:
        return

    seen[p] = True
    # print(p)

    for q in range(len(tree[p])):
        f = p   # from
        d = tree[p][q]  # dist

        key = get_key(f, d)

        if key not in edge_colors.keys():
            this_color_set = g[f] | g[d]
            cand_colors = all_color_set - this_color_set
            if len(cand_colors) > 0:
                g[d].add(min(cand_colors))
                edge_colors[key] = min(cand_colors)
            else:
                edge_colors[key] = color
                g[d].add(color)
                all_color_set.add(color)
                g[p] = g[p] | g[tree[p][q]]
                color += 1

        dfs(tree, tree[p][q], seen, g, color, all_color_set)


seen = [False] * N
all_color_set = set()
dfs(tree, 0, seen, g, 1, all_color_set)

ans = [edge_colors[k] for k in ans.keys()]

print(max(ans))
[print(a) for a in ans]

# [print(k, v) for k, v in edge_colors.items()]

# show_tree(tree, edge_colors)

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


def get_key(p, q):
    v, w = min(p, q), max(p, q)
    return str(v) + "to" + str(w)


def get_color_set(g, key):
    colorset = set()
    fromkey = key.split("to")[0]
    for k, v in g.items():
        if fromkey in k:
            colorset.add(v)

    return colorset


N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]
g = OrderedDict()

for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    g[in1] = set()
    g[in2] = set()


# [print(i, t) for i, t in enumerate(tree)]

edge_colors = OrderedDict()


def dfs(tree, p, seen, g, color, all_color_set):
    if p >= len(tree):
        return

    if seen[p]:
        return

    seen[p] = True
    # print(p)

    for q in range(len(tree[p])):
        f = p   # from
        d = tree[p][q]  # dist

        key = get_key(f, d)

        if key not in edge_colors.keys():
            this_color_set = g[f] | g[d]
            cand_colors = all_color_set - this_color_set
            if len(cand_colors) > 0:
                g[d].add(min(cand_colors))
                edge_colors[key] = min(cand_colors)
            else:
                edge_colors[key] = color
                g[d].add(color)
                all_color_set.add(color)
                g[p] = g[p] | g[tree[p][q]]
                color += 1

        dfs(tree, tree[p][q], seen, g, color, all_color_set)


seen = [False] * N
all_color_set = set()
dfs(tree, 0, seen, g, 1, all_color_set)

ans = [i for k, i in edge_colors.items()]
print(max(ans))
[print(a) for a in ans]