Submission #6385753

---

Source Code Expand

from collections import deque

def dfs(graph, start):
    stack = deque()
    push, pop = stack.append, stack.pop
    counts = [0 for i in range(N+1)]
    push(start)

    ans = []
    cnt = 0
    ncnt = 0
    while stack:
        a = pop()
        keys = [i for i in graph[a].keys()]
        # print(a, keys, counts, ncnt)
        if cnt >= M-1:
            ans.append([a, keys[0]] if counts[a] % 2 == 1 else [keys[0],a])
            counts[a if counts[a] % 2 == 1 else b] += 1
            break
        if len(keys) % 2 == 1:
            b = keys.pop()
            ans.append([b,a])
            counts[b] += 1
            cnt += 1
            del graph[b][a], graph[a][b]
            if not counts[b]:
                push(b)
                visited[b] = 1
                ncnt += 1
        for b in keys:
            # print(ncnt, len(keys), N)
            if ncnt + len(keys) + 1 == N:
                ans.append([a, b] if counts[a] % 2 == 1 else [b, a])
                counts[a if counts[a] % 2 == 1 else b] += 1
                cnt += 1
                # print(a, b, graph[a], graph[b])
                del graph[b][a], graph[a][b]
                if not counts[b]:
                    push(b)
                    ncnt += 1
            else :
                ans.append([a,b])
                counts[a] += 1
                cnt += 1
                del graph[b][a], graph[a][b]
                if not counts[b]:
                    push(b)
                    ncnt += 1
    [print(a,b) for a,b in ans]
    # print(counts, graph)

N,M = map(int, input().split())
graph = {}
for i in range(M-1):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = {}
    if b not in graph:
        graph[b] = {}
    graph[a][b] = graph[b][a] = 1
a,b = map(int, input().split())
if a not in graph:
    graph[a] = {}
if b not in graph:
    graph[b] = {}
graph[a][b] = graph[b][a] = 1
start = a

if M % 2 == 1:
    print(-1)
    exit()
dfs(graph, start)

Submission Info

Judge Result