Problem p02976 (python)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

n, m = map(int, input().split())

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



AB = [[int(x) for x in input().split()] for _ in range(m)]

# representation matrix
repn = [[] for j in range(n + 1)]
for a, b in AB:
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [set() for i in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
q = deque([1])

while q:
    u = q.popleft()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].add(v)
        tree[v].add(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * (n + 1)
ans = []

for a, b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a, b))
    degree[a] += 1


# defining orientations
def dfs(u = 1, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u, v))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v, u))
            degree[v] += 1

dfs()

print('\n'.join(ans))

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

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

# representation matrix
repn = [[] for j in range(n + 1)]
for a, b in AB:
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [set() for i in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
q = deque([1])

while q:
    u = q.popleft()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].add(v)
        tree[v].add(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * (n + 1)
ans = []

for a, b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a, b))
    degree[a] += 1


# defining orientations
def dfs(u = 1, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u, v))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v, u))
            degree[v] += 1

dfs()


# output answer
if degree[1] % 2 == 1:
    print(-1)
else:
    print('\n'.join(ans))

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

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

# representation matrix
repn = [[] for j in range(n + 1)]
for a, b in AB:
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
q = deque([1])

while q:
    u = q.popleft()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].append(v)
        tree[v].append(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * (n + 1)
ans = []

for a, b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a, b))
    degree[a] += 1


# defining orientations
def dfs(u = 1, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u, v))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v, u))
            degree[v] += 1

dfs()


# output answer
if degree[1] % 2 == 1:
    print(-1)
else:
    print('\n'.join(ans))

Buggy submission (verdict: Runtime Error):
n, m = list(map(int, input().split()))
AB = [[int(x) for x in input().split()] for _ in range(m)]

# representation matrix
repn = [[] for j in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [[] for i in range(n)]
visited = [True] + [False] * (n - 1)
q = [0]

while q:
    u = q.pop()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].append(v)
        tree[v].append(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * n
ans = []

for a, b in AB:
    a -= 1
    b -= 1
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a + 1, b + 1))
    degree[a] += 1


# defining orientations
def dfs(u = 0, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u + 1, v + 1))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v + 1, u + 1))
            degree[v] += 1

dfs()


# output answer
if degree[0] % 2 == 1:
    print(-1)
else:
    print('\n'.join(ans))

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

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

# representation matrix
repn = [[] for j in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [[] for i in range(n)]
visited = [True] + [False] * (n - 1)
q = deque([0])

while q:
    u = q.popleft()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].append(v)
        tree[v].append(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * n
ans = []

for a, b in AB:
    a -= 1
    b -= 1
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a + 1, b + 1))
    degree[a] += 1


# defining orientations
def dfs(u = 0, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u + 1, v + 1))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v + 1, u + 1))
            degree[v] += 1

dfs()


# output answer
if degree[0] % 2 == 1:
    print(-1)
else:
    print('\n'.join(ans))

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

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

# representation matrix
repn = [[] for j in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [[] for i in range(n)]
visited = [True] + [False] * (n - 1)
q = deque([0]) # (vertex, depth)

while q:
    u = q.popleft()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].append(v)
        tree[v].append(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * n
ans = []

for a, b in AB:
    a -= 1
    b -= 1
    if b in tree[a]:
        continue
    ans.append([a, b])
    degree[a] += 1


# defining orientations
def dfs(u = 0, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append([u, v])
            degree[u] += 1
        else:
            ans.append([v, u])
            degree[v] += 1

dfs()


# output answer
if degree[0] % 2 == 1:
    print(-1)
else:
    for pair in ans:
        c, d = pair
        c += 1
        d += 1
        print(' '.join(map(str, [c, d])))

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

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

# representation matrix
repn = [[] for j in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [set() for i in range(n)]
visited = [True] + [False] * (n - 1)
q = deque([(0, 0)]) # (vertex, depth)

while q:
    u, d = q.pop()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].add(v)
        tree[v].add(u)
        q.append((v, d + 1))


# define directions of the edges other than that of MST
degree = [0] * n
ans = []

for a, b in AB:
    a -= 1
    b -= 1
    if b in tree[a]:
        continue
    ans.append([a, b])
    degree[a] += 1


# defining orientations
def dfs(u = 0, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append([u, v])
            degree[u] += 1
        else:
            ans.append([v, u])
            degree[v] += 1

dfs()


# output answer
if degree[0] % 2 == 1:
    print(-1)
else:
    for pair in ans:
        c, d = pair
        c += 1
        d += 1
        print(' '.join(map(str, [c, d])))

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

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

# representation matrix
repn = [[] for j in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [[] for i in range(n)]
visited = [True] + [False] * (n - 1)
depth = [0] * n
max_dep = 0
q = deque([(0, 0)]) # (vertex, depth)

while q:
    u, d = q.pop()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].append(v)
        tree[v].append(u)
        depth[v] = d + 1
        max_dep = max(max_dep, d + 1)
        q.append((v, d + 1))


# define directions of the edges other than that of MST
degree = [0] * n
ans = []

for a, b in AB:
    a -= 1
    b -= 1
    if b in tree[a]:
        continue
    ans.append([a, b])
    degree[a] += 1


# defining orientations
def dfs(u = 0, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append([u, v])
            degree[u] += 1
        else:
            ans.append([v, u])
            degree[v] += 1

dfs()


# output answer
if degree[0] % 2 == 1:
    print(-1)
else:
    for pair in ans:
        c, d = pair
        c += 1
        d += 1
        print(' '.join(map(str, [c, d])))