Submission #6382538


Source Code Expand

Copy
from collections import deque

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

    ans = []
    cnt = 0
    while stack:
        a = pop()
        keys = [i for i in graph[a].keys()]
        # print(a, keys)
        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 visited[b]:
                push(b)
                visited[b] = True
        for b in keys:
            ans.append([a,b])
            counts[a] += 1
            cnt += 1
            del graph[b][a], graph[a][b]
            if not visited[b]:
                push(b)
                visited[b] = True
    [print(a,b) for a,b in ans]
    # print(counts)

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

Submission Time
Task B - Even Degrees
User kinetock
Language Python (3.4.3)
Score 0
Code Size 1578 Byte
Status RE
Exec Time 773 ms
Memory 60000 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
AC × 14
WA × 8
RE × 14
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt RE 664 ms 58008 KB
02.txt WA 773 ms 60000 KB
03.txt WA 742 ms 59940 KB
04.txt RE 658 ms 57648 KB
05.txt AC 443 ms 45776 KB
06.txt RE 554 ms 40496 KB
07.txt RE 570 ms 40520 KB
08.txt RE 576 ms 40488 KB
09.txt RE 562 ms 40504 KB
10.txt AC 398 ms 30276 KB
11.txt RE 486 ms 31608 KB
12.txt RE 491 ms 31636 KB
13.txt RE 481 ms 31628 KB
14.txt RE 494 ms 31648 KB
15.txt AC 374 ms 22664 KB
16.txt RE 469 ms 31012 KB
17.txt RE 461 ms 31100 KB
18.txt RE 460 ms 31048 KB
19.txt RE 465 ms 31120 KB
20.txt AC 369 ms 22120 KB
21.txt WA 501 ms 30860 KB
22.txt WA 500 ms 30920 KB
23.txt WA 519 ms 30832 KB
24.txt WA 504 ms 30776 KB
25.txt AC 355 ms 19644 KB
26.txt AC 456 ms 45644 KB
27.txt AC 423 ms 45648 KB
28.txt WA 720 ms 59848 KB
29.txt WA 694 ms 59888 KB
30.txt AC 20 ms 3316 KB
31.txt AC 20 ms 3316 KB
32.txt AC 20 ms 3316 KB
33.txt AC 20 ms 3316 KB
34.txt AC 20 ms 3316 KB
s1.txt AC 21 ms 3316 KB
s2.txt AC 21 ms 3316 KB