Problem p02976 (python)

Fixed submission:
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


N, M = map(int, input().split())
if M%2==1:
    print(-1)
    exit()
E = [set() for _ in range(N+1)]
E_mst = [set() for _ in range(N+1)]
#Closed = [False] * (N+1)
uf = Uf(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)
    if not uf.same(a, b):
        E_mst[a].add(b)
        E_mst[b].add(a)
        uf.unite(a, b)

Cnt = [len(e) for e in E_mst]
q = {i for i, c in enumerate(Cnt) if c==1}
Used = set()
Ans = []
while q:

    v = q.pop()

    #print(E_mst, v)
    # vp = None#E_mst[v][0]
    # for vp_ in E_mst[v]:
    #     if not ((v,vp_) if v<vp_ else (vp_,v)) in Used:
    #         vp = vp_
    #         break
    # else:
    #     break

    if len(E_mst[v])==1:
        vp = E_mst[v].pop()
    else:
        vp = -1

    l = len(E[v])
    #print(v, l)
    for u in E[v].copy():
        if u!=vp:
            v_, u_ = (v,u) if v<u else (u,v)
            if (v_, u_) not in Used:
                Ans.append((v, u))
                E[u].remove(v)
                E[v].remove(u)
                Used.add((v_, u_))
    if l%2==0:
        try:
            E[vp].remove(v)
            E[v].remove(vp)
        except:
            break
        Ans.append((v, vp))
        Used.add((v,vp) if v<vp else (vp,v))
    # Cnt[vp] -= 1
    # if Cnt[vp]==1:
    #     q.add(vp)
    #print(Cnt)

    E_mst[vp].remove(v)
    if len(E_mst[vp])==1:
        q.add(vp)


#print(E_mst)
if len(Ans)!=M:
    print(Ans)
    print(-1)
    assert False
    exit()
for a in Ans:
    print(" ".join(map(str, a)))

Buggy submission (verdict: Runtime Error):
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


N, M = map(int, input().split())
if M%2==1:
    print(-1)
    exit()
E = [set() for _ in range(N+1)]
E_mst = [[] for _ in range(N+1)]
#Closed = [False] * (N+1)
uf = Uf(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)
    if not uf.same(a, b):
        E_mst[a].append(b)
        E_mst[b].append(a)
        uf.unite(a, b)

Cnt = [len(e) for e in E_mst]
q = {i for i, c in enumerate(Cnt) if c==1}
Used = set()
Ans = []
while q:
    v = q.pop()
    vp = None#E_mst[v][0]
    for vp_ in E_mst[v]:
        if not ((v,vp_) if v<vp_ else (vp_,v)) in Used:
            vp = vp_
            break
    else:
        break
    l = len(E[v])
    #print(v, l)
    for u in E[v].copy():
        if u!=vp:
            v_, u_ = (v,u) if v<u else (u,v)
            if (v_, u_) not in Used:
                Ans.append((v, u))
                E[u].remove(v)
                E[v].remove(u)
                Used.add((v_, u_))
    if l%2==0:
        Ans.append((v, vp))
        E[vp].remove(v)
        E[v].remove(vp)
        Used.add((v,vp) if v<vp else (vp,v))
    Cnt[vp] -= 1
    if Cnt[vp]==1:
        q.add(vp)
    #print(Cnt)
#print(E_mst)
if len(Ans)!=M:
    print(Ans)
    print(-1)
    assert False
    exit()
for a in Ans:
    print(" ".join(map(str, a)))