Submission #10163490

---

Source Code Expand

#!/usr/bin/env python3
import numpy as np

stdin = open(0)
data = np.fromstring(stdin.read(), np.int32, sep=' ')
N, M = data[:2]
AB = data[2:2 + N + N]
LR = data[2 + N + N:]
A = AB[::2]
B = AB[1::2]
L = LR[::2]
R = LR[1::2]

ind = np.argsort(A)
A = A[ind]
B = B[ind]

L = np.searchsorted(A, L, 'left').tolist()
R = (np.searchsorted(A, R, 'right')).tolist()
B = np.append(B, 0)
C = np.zeros(len(B), np.int64)
C[1:] = B[:-1] ^ B[1:]
C[0] = B[0]
C = C.tolist()

graph = [[] for _ in range(N + 1)]
for i, (l, r) in enumerate(zip(L, R)):
    if l < r:
        graph[l].append(r)
        graph[r].append(l)

order = []
parent = [0] * (N+1)
close = [0] * (N+1)
for v in range(N):
    if close[v]:
        continue
    stack = [v]
    order.append(v)
    parent[v] = -1
    close[v] = 1
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if close[w]:
                continue
            stack.append(w)
            order.append(w)
            close[w] = 1
            parent[w] = v


E = []
failed = False
for v in order[::-1]:
    if C[v]:
        p = parent[v]
        if p == -1:
            failed = True
            break
        E.append((p, v))
        C[v] = 0
        C[p] ^= 1


if failed:
    print(-1)
else:
    I = {lr: i for i, lr in enumerate(zip(L, R),1)}
    answer = []
    for v, w in E:
        if v > w:
            v, w = w, v
        answer.append(I[(v, w)])
    answer.sort()
    print(len(answer))
    print(*answer)

Submission Info

Judge Result