Problem p02976 (python)

Fixed submission:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
sys.setrecursionlimit(2*10**6)
class UF():
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.size[rx] += self.size[ry] 
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.size[ry] += self.size[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.size[rx] += self.size[ry]
            return True
        return False

def getpar(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[0] = -1
    par[p]  -1
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

def topological_sort_tree(E, r):
    Q = [r]
    L = []
    visited = set([r])
    while Q:
        vn = Q.pop()
        L.append(vn)
        for vf in E[vn]:
            if vf not in visited:
                visited.add(vf)
                Q.append(vf)
    return L

N, M = map(int, readline().split())

Edge = []
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge.append((a, b))

tr = [[] for _ in range(N)]
ans = []
eo = [0]*N
T = UF(N)
for a, b in Edge:
    if T.union(a, b):
        tr[a].append(b)
        tr[b].append(a)
    else:
        ans.append((a+1, b+1))
        eo[a] ^= 1

L = topological_sort_tree(tr, 0)
P = getpar(tr, 0)
for l in L[1:][::-1]:
    if eo[l]:
        ans.append((l+1, P[l]+1))
    else:
        ans.append((P[l]+1, l+1))
        eo[P[l]] ^= 1
if M % 2 == 0:
    for a, b in ans:
        write('{} {}\n'.format(a, b))
else:
    write('-1\n')

Buggy submission (verdict: Runtime Error):
import sys
N, M = map(int, input().split())
if M & 1:
    print(-1)
    sys.exit()
Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1
Ans = []
used = set()
odd = [False]*N
for i in sorted(range(N), key = lambda x: Dim[x]):
    Edge[i].sort(key = lambda x: Dim[x], reverse = True)
    while Dim[i] > 1:
        while (i, Edge[i][-1]) in used:
            Edge[i].pop()
        j1 = Edge[i].pop()
        while (i, Edge[i][-1]) in used:
            Edge[i].pop()
        j2 = Edge[i].pop()
        Ans.append((i+1, j1+1))
        Ans.append((i+1, j2+1))
        Dim[i] -= 2
        Dim[j1] -= 1
        Dim[j2] -= 1
        used.add((i, j1))
        used.add((i, j2))
        used.add((j1, i))
        used.add((j2, i))
assert len(Ans) == M,''

for a in Ans:
    print(*a)

Buggy submission (verdict: Runtime Error):
import sys
N, M = map(int, input().split())
if M & 1:
    print(-1)
    sys.exit()
Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1
Ans = []
used = set()
for i in sorted(range(N), key = lambda x: Dim[x]%2, reverse = True):
    Edge[i].sort(key = lambda x: Dim[x], reverse = True)
    while Dim[i] > 1:
        while (i, Edge[i][-1]) in used:
            Edge[i].pop()
        j1 = Edge[i].pop()
        while (i, Edge[i][-1]) in used:
            Edge[i].pop()
        j2 = Edge[i].pop()
        Ans.append((i+1, j1+1))
        Ans.append((i+1, j2+1))
        Dim[i] -= 2
        Dim[j1] -= 1
        Dim[j2] -= 1
        used.add((i, j1))
        used.add((i, j2))
        used.add((j1, i))
        used.add((j2, i))
assert len(Ans) == M,''

for a in Ans:
    print(*a)

Buggy submission (verdict: Runtime Error):
import sys
N, M = map(int, input().split())
if M & 1:
    print(-1)
    sys.exit()
Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1
Ans = []
used = set()
for i in range(N):
    Edge[i].sort(key = lambda x: Dim[x], reverse = True)
    while Dim[i] > 1:
        while (i, Edge[i][-1]) in used:
            Edge[i].pop()
        j1 = Edge[i].pop()
        while (i, Edge[i][-1]) in used:
            Edge[i].pop()
        j2 = Edge[i].pop()
        Ans.append((i+1, j1+1))
        Ans.append((i+1, j2+1))
        Dim[i] -= 2
        Dim[j1] -= 1
        Dim[j2] -= 1
        used.add((i, j1))
        used.add((i, j2))
        used.add((j1, i))
        used.add((j2, i))
assert len(Ans) == M,''

for a in Ans:
    print(*a)