Problem p02976 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush
from collections import defaultdict

n,m = map(int,readline().split())
ab = list(map(int,read().split()))

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

it = iter(ab)
links = [[] for _ in range(n+1)]
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

depth = [-1] * (n+1)
parent = [0] * (n+1)
child = [set() for _ in range(n+1)]
hq_dep = []

stack = [1]
depth[1] = 0
# heappush(hq_dep, (0,1))
now_dep = 1
while(stack):
    stack2 = []
    while(stack):
        i = stack.pop()
        for j in links[i]:
            if(depth[j] == -1):
                depth[j] = now_dep
                parent[j] = i
                heappush(hq_dep,(now_dep*-1,j))
                stack2.append(j)
            else:
                child[j].add(i)
    now_dep += 1
    stack = stack2[::]

# 0:未定　1:done
ans = []
d = defaultdict(int)
outs = [0] * (n+1)
while(hq_dep):
    i_dep,i = heappop(hq_dep)
    for j in child[i]:
        if(d[min(i,j)*10**6 + max(i,j)] == 0):
            d[min(i,j)*10**6 + max(i,j)] = 1
            outs[j] += 1
            ans.append([j,i])
    j = parent[i]
    if(outs[i]%2==1):
        d[min(i,j)*10**6 + max(i,j)] = 1
        outs[i] += 1
        ans.append([i,j])
    else:
        d[min(i,j)*10**6 + max(i,j)] = 1
        outs[j] += 1
        ans.append([j,i])

print('\n'.join(map(lambda x: ' '.join(map(str,x)), ans)))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
ab = list(map(int,read().split()))

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

it = iter(ab)
links = [[] for _ in range(n+1)]
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

depth = [-1] * (n+1)
parent = [0] * (n+1)
child = [set() for _ in range(n+1)]
hq_dep = []

stack = [1]
depth[1] = 0
heappush(hq_dep, (0,1))
now_dep = 1
while(stack):
    stack2 = []
    while(stack):
        i = stack.pop()
        for j in links[i]:
            if(depth[j] == -1):
                depth[j] = now_dep
                parent[j] = i
                heappush(hq_dep,(now_dep*-1,j))
                stack2.append(j)
            else:
                child[j].add(i)
    now_dep += 1
    stack = stack2[::]

# print(parent)
# print(child)
# print(d)
# print(hq_dep)

ans = []
for _ in range(m//2):
    while(True):
        i_dep,i= hq_dep[0]
        if(not child[i]):
            heappop(hq_dep)
        else:
            break

    if(len(child[i]) >= 2):
        j = child[i].pop()
        k = child[i].pop()
        child[j].remove(i)
        child[k].remove(i)

    else:
        j = child[i].pop()
        k = parent[i]
        parent[i] = 0
        if(i in child[j]):
            child[j].remove(i)


    ans.append((i,j))
    ans.append((i,k))



print('\n'.join(map(lambda x: ' '.join(map(str,x)), ans)))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush
from collections import defaultdict

n,m = map(int,readline().split())
ab = list(map(int,read().split()))

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

it = iter(ab)
links = [[] for _ in range(n+1)]
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

depth = [-1] * (n+1)
parent = [0] * (n+1)
child = [set() for _ in range(n+1)]
hq_dep = []
d = defaultdict(int)

stack = [1]
depth[1] = 0
heappush(hq_dep, (0,1))
now_dep = 1
while(stack):
    stack2 = []
    while(stack):
        i = stack.pop()
        for j in links[i]:
            if(depth[j] == -1):
                depth[j] = now_dep
                parent[j] = i
                d[i*10**6+j] = 1
                heappush(hq_dep,(now_dep*-1,j))
                stack2.append(j)
            else:
                child[j].add(i)
    now_dep += 1
    stack = stack2[::]

# print(parent)
# print(child)
# print(d)
# print(hq_dep)

ans = []
for _ in range(m//2):
    while(True):
        i_dep,i= hq_dep[0]
        if(parent[i]==0):
            heappop(hq_dep)
        else:
            break

    if(child[i]):
        j = child[i].pop()
        if(child[i]):
            k = child[i].pop()
        else:
            k = parent[i]
            parent[i] = 0

        if(parent[j]==i):
            parent[j] = 0
        else:
            child[j].remove(i)
        if(parent[k]==i):
            parent[k] = 0
        else:
            child[k].remove(i)

        ans.append((i,j))
        ans.append((i,k))


    else:
        j = parent[i]
        child[j].remove(i)
        heappop(hq_dep)
        if(child[j]):
            k = child[j].pop()
        else:
            k = parent[j]
            parent[j] = 0
        if(parent[k]==j):
            parent[k] = 0
        else:
            child[k].remove(j)

        ans.append((j,i))
        ans.append((j,k))


print('\n'.join(map(lambda x: ' '.join(map(str,x)), ans)))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush
from collections import defaultdict

n,m = map(int,readline().split())
ab = list(map(int,read().split()))

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

it = iter(ab)
links = [[] for _ in range(n+1)]
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

depth = [-1] * (n+1)
parent = [0] * (n+1)
child = [set() for _ in range(n+1)]
hq_dep = []
d = defaultdict(int)

stack = [1]
depth[1] = 0
heappush(hq_dep, (0,1))
now_dep = 1
while(stack):
    stack2 = []
    while(stack):
        i = stack.pop()
        for j in links[i]:
            if(depth[j] == -1):
                depth[j] = now_dep
                parent[j] = i
                d[i*10**6+j] = 1
                heappush(hq_dep,(now_dep*-1,j))
                stack2.append(j)
            else:
                child[j].add(i)
    now_dep += 1
    stack = stack2[::]

# print(parent)
# print(child)
# print(d)
# print(hq_dep)

ans = []
for _ in range(m//2):
    while(True):
        i_dep,i= hq_dep[0]
        if(parent[i]==0):
            heappop(hq_dep)
        else:
            break

    if(child[i]):
        j = child[i].pop()
        if(child[i]):
            k = child[i].pop()
        else:
            k = parent[i]
            parent[i] = 0

        if(parent[j]==i):
            parent[j] = 0
        else:
            child[j].remove(i)
        if(parent[k]==i):
            parent[k] = 0
        else:
            child[k].remove(i)

        ans.append((i,j))
        ans.append((i,k))


    else:
        j = parent[i]
        child[j].remove(i)
        heappop(hq_dep)
        if(child[j]):
            k = child[j].pop()
        else:
            k = parent[j]
            parent[j] = 0
        if(parent[k]==j):
            parent[k] = 0
        else:
            child[k].remove(i)

        ans.append((j,i))
        ans.append((j,k))


print('\n'.join(map(lambda x: ' '.join(map(str,x)), ans)))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush
from collections import defaultdict

n,m = map(int,readline().split())
ab = list(map(int,read().split()))

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

it = iter(ab)
links = [[] for _ in range(n+1)]
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

hqs = [[] for _ in range(n+1)]
depth = [-1] * (n+1)
hq_dep = []
d = defaultdict(int)

stack = [1]
depth[1] = 0
heappush(hq_dep, (0,1))
now_dep = 1
while(stack):
    stack2 = []
    while(stack):
        i = stack.pop()
        for j in links[i]:
            if(depth[j] == -1):
                depth[j] = now_dep
                heappush(hq_dep,(now_dep*-1,j))
                stack2.append(j)
            heappush(hqs[i], (depth[j]*-1,j))
            if(i<j):
                d[i*10**6+j] = 1

    now_dep += 1
    stack = stack2[::]

ans = []
for _ in range(m//2):
    while(True):
        i_dep,i = hq_dep[0]
        j_dep,j = heappop(hqs[i])
        if(not hqs[i]):
            heappop(hq_dep)
        if(d[min(i,j)*10**6 + max(i,j)]==1):
            d[min(i,j)*10**6 + max(i,j)] = 0
            break


    if(not hqs[i]):
        i,j = j,i

    while(True):
        k_dep,k = heappop(hqs[i])
        if(not hqs[i]):
            heappop(hq_dep)
        if(d[min(i,k)*10**6 + max(i,k)]==1):
            d[min(i,k)*10**6 + max(i,k)] = 0
            break
        if(not hqs[i]):
            i,j = j,i

    ans.append((i,j))
    ans.append((i,k))

print('\n'.join(map(lambda x: ' '.join(map(str,x)), ans)))