Problem p02976 (python)

Fixed submission:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 5)


def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return

    tree = [set() for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if parents[u] == -1:
                tree[v].add(u)
                parents[u] = v
                q.append(u)
            links[u].remove(v)

    parities = [len(l) % 2 for l in links]

    # print(links)
    # print(tree)
    # print(parents)
    # print(parities)

    def dfs(v):
        b = parities[v]
        for u in tree[v]:
            c = dfs(u)
            b ^= c
        if b:
            p = parents[v]
            links[p].remove(v)
            links[v].add(p)
        return b

    dfs(0)

    ans = ['{} {}'.format(v + 1, u + 1) for v in range(n) for u in links[v]]
    print('\n'.join(ans))


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

links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

solve(n, m, links)

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


def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return

    going = [set() for _ in range(n)]
    tree = [{} for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if v in going[u]:
                continue
            going[v].add(u)
            if parents[u] == -1:
                tree[v][u] = 0
                parents[u] = v
            q.append(u)

    parities = [len(l) % 2 for l in going]

    # print(going)
    # print(tree)
    # print(parents)
    # print(parities)

    def dfs(v):
        b = parities[v]
        for u in tree[v]:
            c = dfs(u)
            b ^= c
        if b:
            p = parents[v]
            if p != -1:
                going[p].remove(v)
                going[v].add(p)
        return b

    dfs(0)

    ans = ['{} {}'.format(v + 1, u + 1) for v in range(n) for u in going[v]]
    print('\n'.join(ans))


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

links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

solve(n, m, links)

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


def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return

    going = [set() for _ in range(n)]
    tree = [{} for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if v in going[u]:
                continue
            going[v].add(u)
            if parents[u] == -1:
                tree[v][u] = 0
                parents[u] = v
            q.append(u)

    parities = [len(l) % 2 for l in going]

    # print(going)
    # print(tree)
    # print(parents)
    # print(parities)

    def dfs(v):
        b = parities[v]
        for u in tree[v]:
            c = dfs(u)
            b ^= c
        if b:
            p = parents[v]
            if p != -1:
                tree[p][v] ^= 1
        return b

    dfs(0)

    ans = []
    for v in range(n):
        for u in going[v]:
            if u not in tree[v]:
                ans.append('{} {}'.format(v + 1, u + 1))
            elif tree[v][u] == 0:
                ans.append('{} {}'.format(v + 1, u + 1))
            else:
                ans.append('{} {}'.format(u + 1, v + 1))
    print('\n'.join(ans))


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

links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

solve(n, m, links)

Buggy submission (verdict: Runtime Error):
import sys


def solve(n, m, links, parents):
    if m % 2 == 1:
        print(-1)
        return

    fixed = [len(l) % 2 == 0 for l in links]

    def reverse_links(s, t):
        v = s
        while v != t:
            p = parents[v]
            links[p][v] ^= 1
            v = p

    tmp_trace = set()
    tmp_pair = -1
    for v in range(n):
        if fixed[v]:
            continue
        if tmp_pair == -1:
            u = v
            while u != -1:
                tmp_trace.add(u)
                u = parents[u]
            tmp_pair = v
        else:
            u = v
            while u != -1:
                if u in tmp_trace:
                    reverse_links(v, u)
                    reverse_links(tmp_pair, u)
                    break
                u = parents[u]
            else:
                raise AssertionError
            fixed[v] = fixed[tmp_pair] = True
            tmp_trace.clear()
            tmp_pair = -1

        # print(v, tmp_trace, tmp_pair)

    assert tmp_pair == -1

    ans = []
    for v in range(n):
        for u, d in links[v].items():
            if d == 0:
                ans.append('{} {}'.format(v + 1, u + 1))
            else:
                ans.append('{} {}'.format(u + 1, v + 1))
    print('\n'.join(ans))


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

first_links = []
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    first_links.append((a, b))
first_links.sort()

links = [{} for _ in range(n)]
parents = [-1] * n
for a, b in first_links:
    links[a][b] = 0
    if parents[b] == -1:
        parents[b] = a

# print(links)
# print(parents)

solve(n, m, links, parents)

Buggy submission (verdict: Runtime Error):
import sys


def solve(n, m, links, parents):
    if m % 2 == 1:
        print(-1)
        return

    fixed = [len(l) % 2 == 0 for l in links]

    def reverse_links(s, t):
        v = s
        while v != t:
            p = parents[v]
            links[p][v] ^= 1
            v = p

    tmp_trace = set()
    tmp_pair = -1
    for v in range(n):
        if fixed[v]:
            continue
        if tmp_pair == -1:
            u = v
            while u != -1:
                tmp_trace.add(u)
                u = parents[u]
            tmp_pair = v
        else:
            u = v
            while u != -1:
                if u in tmp_trace:
                    reverse_links(v, u)
                    reverse_links(tmp_pair, u)
                    break
                u = parents[u]
            else:
                raise AssertionError
            tmp_trace.clear()
            tmp_pair = -1

        # print(v, tmp_vertices, tmp_pair)

    assert tmp_pair == -1

    ans = []
    for v in range(n):
        for u, d in links[v].items():
            if d == 0:
                ans.append('{} {}'.format(v + 1, u + 1))
            else:
                ans.append('{} {}'.format(u + 1, v + 1))
    print('\n'.join(ans))


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

first_links = []
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    first_links.append((a, b))
first_links.sort()

links = [{} for _ in range(n)]
parents = [-1] * n
for a, b in first_links:
    links[a][b] = 0
    if parents[b] == -1:
        parents[b] = a

solve(n, m, links, parents)

Buggy submission (verdict: Runtime Error):
import sys


def solve(n, m, links, parents):
    if m % 2 == 1:
        print(-1)
        return

    fixed = [len(l) % 2 == 0 for l in links]

    def reverse_links(s, t):
        v = s
        while v != t:
            p = parents[v]
            links[p][v] ^= 1
            v = p

    tmp_trace = set()
    tmp_pair = -1
    for v in range(n):
        if fixed[v]:
            continue
        if tmp_pair == -1:
            u = v
            while u != -1:
                tmp_trace.add(u)
                u = parents[u]
            tmp_pair = v
        else:
            u = v
            while u != -1:
                if u in tmp_trace:
                    reverse_links(v, u)
                    reverse_links(tmp_pair, u)
                    break
                u = parents[u]
            else:
                raise AssertionError
            tmp_trace.clear()
            tmp_pair = -1

        # print(v, tmp_vertices, tmp_pair)

    assert tmp_pair == -1

    ans = []
    for v in range(n):
        for u, d in links[v].items():
            if d == 0:
                ans.append('{} {}'.format(v + 1, u + 1))
            else:
                ans.append('{} {}'.format(u + 1, v + 1))
    print('\n'.join(ans))


n, m = list(map(int, input().split()))
links = [{} for _ in range(n)]
parents = [-1] * n
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    links[a][b] = 0
    parents[b] = a
solve(n, m, links, parents)

Buggy submission (verdict: Runtime Error):
import sys


def solve(n, m, links, parents):
    if m % 2 == 1:
        print(-1)
        return

    fixed = [len(l) % 2 == 0 for l in links]

    def reverse_links(s, t):
        v = s
        while v != t:
            p = parents[v]
            links[p][v] ^= 1
            v = p

    # print(links)
    # print(parents)
    # print(fixed)

    tmp_vertices = set()
    tmp_pair = -1
    for v in range(n - 1, -1, -1):
        if fixed[v]:
            continue
        exist_pair = tmp_pair != -1
        p = parents[v]
        if not exist_pair:
            tmp_vertices.add(v)
            while p != -1:
                tmp_vertices.add(p)
                p = parents[p]
        elif v == 0:
            reverse_links(tmp_pair, v)
        else:
            # print(v, u, p, exist_pair, tmp_vertices, tmp_pair)
            while p != -1:
                if p in tmp_vertices:
                    reverse_links(v, p)
                    reverse_links(tmp_pair, p)
                    break
                p = parents[p]
        if exist_pair:
            tmp_vertices.clear()
            tmp_pair = -1
        else:
            tmp_pair = v

    ans = []
    for v in range(n):
        for u, d in links[v].items():
            if d == 0:
                ans.append('{} {}'.format(v + 1, u + 1))
            else:
                ans.append('{} {}'.format(u + 1, v + 1))
    print('\n'.join(ans))


n, m = list(map(int, input().split()))
links = [{} for _ in range(n)]
parents = [-1] * n
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    links[a][b] = 0
    parents[b] = a
solve(n, m, links, parents)

Buggy submission (verdict: Runtime Error):
import sys


def solve(n, m, links, parents):
    if m % 2 == 1:
        print(-1)
        return

    fixed = [len(l) % 2 == 0 for l in links]

    def reverse_links(s, t):
        v = s
        while v != t:
            p = parents[v]
            links[p][v] ^= 1
            v = p

    # print(links)
    # print(parents)
    # print(fixed)

    tmp_vertices = set()
    tmp_pair = -1
    for v in range(n - 1, -1, -1):
        if fixed[v]:
            continue
        exist_pair = tmp_pair != -1
        u = v
        p = parents[v]
        if not exist_pair:
            tmp_vertices.add(u)
        if v == 0 and exist_pair:
            reverse_links(tmp_pair, v)
        else:
            # print(v, u, p, exist_pair, tmp_vertices, tmp_pair)
            while p != -1:
                if not exist_pair:
                    tmp_vertices.add(p)
                else:
                    if p in tmp_vertices:
                        reverse_links(v, p)
                        reverse_links(tmp_pair, p)
                u = p
                p = parents[u]
        if exist_pair:
            tmp_vertices.clear()
            tmp_pair = -1
        else:
            tmp_pair = v

    ans = []
    for v in range(n):
        for u, d in links[v].items():
            if d == 0:
                ans.append('{} {}'.format(v + 1, u + 1))
            else:
                ans.append('{} {}'.format(u + 1, v + 1))
    print('\n'.join(ans))


n, m = list(map(int, input().split()))
links = [{} for _ in range(n)]
parents = [-1] * n
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    links[a][b] = 0
    parents[b] = a
solve(n, m, links, parents)