Problem p02976 (python)

Fixed submission:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) > 0 and v != 1:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        if v in G[c]:
            G[c].remove(v)
        stack.append(c)
    G[v] = set()
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) > 0 and v != 1:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        if v in G[c]:
            G[c].remove()
        stack.append(c)
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) > 0 and v != 1:
        if parent[v] < 0 or N < parent[v]:
            print(-1)
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        if v not in G[c]:
            print(-1)
        G[c].remove(v)
        stack.append(c)
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) > 0 and v != 1:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        G[c].remove(v)
        stack.append(c)
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
print(-1)
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) == 0:
        continue
    if parent[v] != 0:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        G[c].remove(v)
        stack.append(c)
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        if v == 1:
            print(-1)
            exit()
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) == 0:
        continue
    if parent[v] != 0:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        G[c].remove(v)
        stack.append(c)
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)