Submission #6385753


Source Code Expand

Copy
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

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
AC × 14
WA × 21
RE × 1
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 WA 451 ms 46484 KB
02.txt WA 440 ms 46528 KB
03.txt WA 451 ms 46512 KB
04.txt WA 441 ms 46512 KB
05.txt AC 443 ms 45792 KB
06.txt WA 662 ms 41864 KB
07.txt WA 675 ms 42260 KB
08.txt WA 656 ms 42244 KB
09.txt WA 684 ms 42008 KB
10.txt AC 392 ms 30340 KB
11.txt WA 666 ms 34176 KB
12.txt WA 677 ms 34192 KB
13.txt WA 660 ms 34192 KB
14.txt WA 642 ms 34184 KB
15.txt AC 381 ms 22692 KB
16.txt WA 673 ms 33676 KB
17.txt WA 693 ms 33764 KB
18.txt WA 656 ms 33912 KB
19.txt WA 636 ms 33768 KB
20.txt AC 385 ms 22120 KB
21.txt WA 445 ms 24252 KB
22.txt RE 539 ms 29516 KB
23.txt WA 412 ms 22960 KB
24.txt AC 768 ms 31728 KB
25.txt AC 351 ms 19516 KB
26.txt AC 436 ms 45652 KB
27.txt AC 432 ms 45648 KB
28.txt WA 429 ms 46408 KB
29.txt WA 444 ms 46324 KB
30.txt AC 20 ms 3316 KB
31.txt AC 21 ms 3316 KB
32.txt WA 20 ms 3316 KB
33.txt AC 21 ms 3316 KB
34.txt AC 20 ms 3316 KB
s1.txt AC 21 ms 3316 KB
s2.txt AC 20 ms 3316 KB