Problem p02976 (python)

Fixed submission:
from collections import deque

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

if m % 2:
    print(-1)
    exit()

adj = [[] for _ in range(n + 1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

s = 1
dq = deque([s])
d = [-1] * (n + 1)
d[s] = 0
p = [-1] * (n + 1)
order = []
while dq:
    u = dq.popleft()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            p[v] = u
            dq.append(v)

out = [0] * (n + 1)
ans = []
for a, b in ab:
    if p[a] == b or p[b] == a:
        continue
    ans.append((a, b))
    out[a] ^= 1

for v in order[1:][::-1]:
    u = p[v]
    if out[v]:
        ans.append((v, u))
        out[v] ^= 1
    else:
        ans.append((u, v))
        out[u] ^= 1

for u, v in ans:
    print(u, v)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict, deque

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

if m % 2:
    print(-1)
    exit()

adj = [[] for _ in range(n + 1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

s = 1
dq = deque([s])
d = [-1] * (n + 1)
d[s] = 0
p = [-1] * (n + 1)
order = []
while dq:
    u = dq.popleft()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            p[v] = u
            dq.append(v)

out = [0] * (n + 1)
ans = []
for a, b in ab:
    if p[a] == b or p[b] == a:
        continue
    ans.append((a, b))
    out[a] ^= 1

for v in order[1:][::-1]:
    u = p[v]
    if out[v]:
        ans.append((v, u))
        out[v] ^= 1
    else:
        ans.append((u, v))
        out[u] ^= 1

for u, v in ans:
    print(u, v)

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

INF = (1 << 31) - 1


class SegmentTree:
    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.data = [[INF, INF]] * (2 * self.n - 1)

    def update(self, i, a):
        """Update list[i] (0-indexed)"""
        idx = i
        i += self.n - 1
        self.data[i] = [a, idx]
        while i > 0:
            i = (i - 1) // 2
            vl, il = self.data[i*2+1]
            vr, ir = self.data[i*2+2]
            if vr < vl:
                self.data[i] = [vr, ir]
            else:
                self.data[i] = [vl, il]

    def find(self, begin, end, i=0, l=0, r=None):
        """
        Find value from index begin <= idx < end.
        :param begin: begin index to search through (for list)
        :param end: end index to search through (for list)
        :param i: node index (for self.data)
        :param l: begin index of looking node (for list)
        :param r: end index of looking node (for list)
        :return: value
        """
        if r is None:
            r = self.n

        if r <= begin or end <= l:
            return [INF, INF]

        if begin <= l and r <= end:
            return self.data[i]

        else:
            vl, il = self.find(begin, end, i * 2 + 1, l, (l + r) // 2)
            vr, ir = self.find(begin, end, i * 2 + 2, (l + r) // 2, r)
            if vr < vl:
                ret = [vr, ir]
            else:
                ret = [vl, il]

            return ret


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

if m % 2:
    print(-1)
    exit()

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

seg = SegmentTree(n)
for i, li in enumerate(adj):
    seg.update(i, len(li))

used = defaultdict(int)
out = [0] * n
for _ in range(n):
    _, u = seg.find(0, n)
    add = []
    for v in adj[u]:
        if not used[(v, u)]:
            add.append(v)

    for v in add:
        used[(u, v)] = 1
        val, i = seg.find(v, v+1)
        seg.update(v, val-1)
        out[u] ^= 1

    if out[u]:
        v = add[-1]
        used[(u, v)] = -1
        out[u] ^= 1
        out[v] ^= 1

    seg.update(u, INF)

for (u, v), val in used.items():
    u += 1
    v += 1
    if val == 1:
        print(u, v)
    elif val == -1:
        print(v, u)