AtCoder Beginner Contest 155 - Perils in Parallel

After being invaded by the Kingdom of AlDebaran, bombs are planted throughout our country, AtCoder Kingdom.
Fortunately, our military team called ABC has managed to obtain a device that is a part of the system controlling the bombs.
There are N bombs, numbered 1 to N, planted in our country. Bomb i is planted at the coordinate A_i. It is currently activated if B_i=1, and deactivated if B_i=0.
The device has M cords numbered 1 to M. If we cut Cord j, the states of all the bombs planted between the coordinates L_j and R_j (inclusive) will be switched - from activated to deactivated, and vice versa.
Determine whether it is possible to deactivate all the bombs at the same time. If the answer is yes, output a set of cords that should be cut.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^5
 - 1 \leq A_i \leq 10^9\ (1 \leq i \leq N)
 - A_i are pairwise distinct.
 - B_i is 0 or 1. (1 \leq i \leq N)
 - 1 \leq M \leq 2 \times 10^5
 - 1 \leq L_j \leq R_j \leq 10^9\ (1 \leq j \leq M)

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1
:
A_N B_N
L_1 R_1
:
L_M R_M

-----Output-----
If it is impossible to deactivate all the bombs at the same time, print -1. If it is possible to do so, print a set of cords that should be cut, as follows:
k
c_1 c_2 \dots c_k

Here, k is the number of cords (possibly 0), and c_1, c_2, \dots, c_k represent the cords that should be cut. 1 \leq c_1 < c_2 < \dots < c_k \leq M must hold.

-----Sample Input-----
3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9

-----Sample Output-----
2
1 4

There are two activated bombs at the coordinates 5, 10, and one deactivated bomb at the coordinate 8.
Cutting Cord 1 switches the states of all the bombs planted between the coordinates 1 and 10, that is, all of the three bombs.
Cutting Cord 4 switches the states of all the bombs planted between the coordinates 8 and 9, that is, Bomb 3.
Thus, we can deactivate all the bombs by cutting Cord 1 and Cord 4.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[0])
A = [ab[0] for ab in AB]
B = [ab[1] for ab in AB]
Bd = [B[0]] + [B[i + 1] ^ B[i] for i in range(N - 1)] + [B[N - 1]]
import bisect
E = [set() for _ in range(N + 1)]
for i in range(M):
	(L, R) = map(int, input().split())
	l = bisect.bisect_left(A, L)
	r = bisect.bisect_right(A, R)
	E[l].add((r, i + 1))
	E[r].add((l, i + 1))
used = [False for _ in range(N + 1)]
ans = []

def dfs(x):
	used[x] = True
	rslt = Bd[x]
	for (to, i) in E[x]:
		if used[to]:
			continue
		r = dfs(to)
		if r:
			ans.append(i)
		rslt ^= r
	return rslt
for i in range(N + 1):
	if used[i]:
		continue
	r = dfs(i)
	if r:
		print(-1)
		exit()
print(len(ans))
print(' '.join(map(str, sorted(ans))))


import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(v, x, g, used, ans):
	used[v] = True
	res = x[v]
	for e in g[v]:
		if used[e[0]]:
			continue
		r = dfs(e[0], x, g, used, ans)
		if r:
			ans.append(e[1])
		res ^= r
	return res

def main():
	(n, m) = map(int, input().split())
	ab = [[] for _ in range(n)]
	ans = []
	g = [[] for _ in range(n + 1)]
	used = [False] * (n + 1)
	for i in range(n):
		ab[i] = list(map(int, input().split()))
	ab = sorted(ab, key=lambda x: x[0])
	al = list(map(lambda x: x[0], ab))
	for i in range(m):
		(l, r) = map(int, input().split())
		l = bisect.bisect_left(al, l)
		r = bisect.bisect_right(al, r)
		g[l].append((r, i + 1))
		g[r].append((l, i + 1))
	x = [0] * (n + 1)
	x[0] = ab[0][1]
	for i in range(n - 1):
		x[i + 1] = ab[i][1] ^ ab[i + 1][1]
	x[n] = ab[n - 1][1]
	for i in range(n + 1):
		if used[i]:
			continue
		if dfs(i, x, g, used, ans):
			print(-1)
			return
	ans.sort()
	print(len(ans))
	print(*ans)
main()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n, m) = map(int, readline().split())
ab = [tuple(map(int, readline().split())) for _ in range(n)]
lr = [tuple(map(int, readline().split())) for _ in range(m)]
ab.sort()
a = []
b = []
for (i, j) in ab:
	a.append(i)
	b.append(j)
from bisect import *
g = [[] for _ in range(n + 1)]
lidx = []
ridx = []
for i in range(m):
	(l, r) = lr[i]
	li = bisect_left(a, l)
	ri = bisect_right(a, r)
	if li != ri:
		lidx.append(li)
		ridx.append(ri)
		g[li].append((ri, i + 1))
		g[ri].append((li, i + 1))
b.append(0)
for i in range(n - 1, -1, -1):
	b[i + 1] ^= b[i]
q = [0]
parent = [-1] * (n + 1)
edge_idx = [-1] * (n + 1)
order = []
for i in range(n, -1, -1):
	if parent[i] == -1:
		q = [i]
		while q:
			v = q.pop()
			order.append(v)
			if parent[v] == -1:
				parent[v] = -2
			for (c, idx) in g[v]:
				if parent[c] == -1:
					parent[c] = v
					edge_idx[c] = idx
					q.append(c)
ans = []
for i in order[::-1]:
	if b[i] and parent[i] != -2:
		b[i] = 0
		b[parent[i]] ^= 1
		ans.append(edge_idx[i])
if all((not i for i in b[:-1])):
	print(len(ans))
	print(*sorted(ans))
else:
	print(-1)


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()
from bisect import bisect_left, bisect_right

def resolve():
	(n, m) = map(int, input().split())
	AB = [list(map(int, input().split())) for _ in range(n)]
	AB.sort()
	AB.append([INF, 0])
	X = [0] * (n + 1)
	X[0] = AB[0][1]
	for i in range(n, 0, -1):
		AB[i][1] ^= AB[i - 1][1]
	E = [[] for _ in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		l = bisect_left(AB, [u, 0])
		r = bisect_right(AB, [v, 1])
		E[l].append((r, i + 1))
		E[r].append((l, i + 1))
	ans = []
	used = [False] * (n + 1)

	def dfs(v):
		used[v] = True
		res = AB[v][1]
		for (nv, i) in E[v]:
			if used[nv]:
				continue
			r = dfs(nv)
			if r:
				ans.append(i)
			res ^= r
		return res
	for v in range(n + 1):
		if used[v]:
			continue
		if dfs(v):
			print(-1)
			return
	print(len(ans))
	if ans:
		print(*sorted(ans))
resolve()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import bisect
(n, m) = map(int, input().split())
seen = set()
ab = []
for _ in range(n):
	(a, b) = map(int, input().split())
	ab.append((a, b))
	seen.add(a)
ab.sort()
seen_list = list(seen)
seen_list.sort()
comp = dict()
comp_inv = dict()
for (i, item) in enumerate(seen_list):
	comp[item] = i
	comp_inv[i] = item
node_num = len(comp)
d = [0] * (node_num + 1)
prev = 0
for (a, b) in ab:
	if b != prev:
		d[comp[a]] = 1
	prev = b
if prev != 0:
	d[node_num] = 1
switch_dict = dict()
lr = []
for i in range(m):
	(l, r) = map(int, input().split())
	lft = bisect.bisect_left(seen_list, l)
	rgt = bisect.bisect_right(seen_list, r)
	if lft != rgt:
		lr.append((lft, rgt))
		switch_dict[lft, rgt] = i + 1
edge = [[] for _ in range(node_num + 1)]
for (l, r) in lr:
	edge[l].append(r)
	edge[r].append(l)
visited = [0] * (node_num + 1)
ans = []

def dfs(p, v):
	ret = d[v]
	for nv in edge[v]:
		if nv == p:
			continue
		if not visited[nv]:
			visited[nv] = 1
			val = dfs(v, nv)
			if val == 1:
				if v < nv:
					ans.append(switch_dict[v, nv])
				else:
					ans.append(switch_dict[nv, v])
				ret += 1
	return ret % 2
for i in range(node_num + 1):
	if visited[i]:
		continue
	visited[i] = 1
	ret = dfs(-1, i)
	if ret == 1:
		print(-1)
		return
for (c, is_visited) in zip(d, visited):
	if not is_visited and c:
		print(-1)
		return
ans.sort()
print(len(ans))
print(*ans)


import bisect
import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(N, M) = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
LR = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
AB.sort()
odd = 0
nums = [(0, 0)] + AB + [(INF, 0)]
A = [a for (a, b) in nums]
B = [b for (a, b) in nums]
size = len(nums)
graph = [[] for _ in range(size)]
for (i, (l, r)) in enumerate(LR, start=1):
	v = bisect.bisect_left(A, l) - 1
	u = bisect.bisect_right(A, r) - 1
	graph[v].append((u, i))
	graph[u].append((v, i))
parity = [0] * size
for (i, (b1, b2)) in enumerate(zip(B, B[1:])):
	if b1 == 0 and b2 == 1:
		parity[i] = 1
	if b1 == 1 and b2 == 0:
		parity[i] = 1
seen = [False] * size
trees = []
for root in range(size):
	if seen[root] or not graph[root]:
		continue
	edges = []
	seen[root] = True
	stack = [root]
	while stack:
		v = stack.pop()
		for (u, i) in graph[v]:
			if seen[u]:
				continue
			seen[u] = True
			stack.append(u)
			edges.append((v, u, i))
	if not edges and parity[root] == 1:
		print(-1)
		exit()
	trees.append(edges)
graph = [[] for _ in range(size)]
degrees = [0] * size
for edges in trees:
	for (v, u, i) in edges:
		graph[v].append((u, i))
		graph[u].append((v, i))
		degrees[v] += 1
		degrees[u] += 1
ans = []
seen = [False] * size
stack = []
for (v, d) in enumerate(degrees):
	if d == 1:
		stack.append(v)
while stack:
	v = stack.pop()
	if degrees[v] == 0:
		continue
	assert degrees[v] == 1
	if seen[v]:
		continue
	seen[v] = True
	degrees[v] = 0
	for (u, i) in graph[v]:
		if seen[u]:
			continue
		if parity[v] == parity[u] == 1:
			parity[u] = parity[v] = 0
			ans.append(i)
		elif parity[v] == 1 and parity[u] == 0:
			parity[u] = 1
			parity[v] = 0
			ans.append(i)
		degrees[u] -= 1
		if degrees[u] == 1:
			stack.append(u)
if 1 in parity:
	print(-1)
else:
	print(len(ans))
	print(*sorted(ans))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left, bisect_right
(N, M) = map(int, input().split())
AB = [[0, 0]] + [[int(i) for i in input().split()] for _ in range(N)] + [[1 << 40, 0]]
LR = [[int(i) for i in input().split()] for _ in range(M)]
N += 2
compressed = sorted([a for (a, b) in AB])
bomb = [0] * N
for (a, b) in AB:
	a = bisect_left(compressed, a)
	bomb[a] = b
diff = [bomb[i - 1] ^ bomb[i] for i in range(1, N)]
vec = [[] for _ in range(N)]
convert = {}
for (i, (l, r)) in enumerate(LR):
	if compressed[-1] < l or r < compressed[0]:
		continue
	l = bisect_left(compressed, l) - 1
	r = bisect_right(compressed, r) - 1
	if r <= l:
		continue
	vec[l].append(r)
	vec[r].append(l)
	convert[l, r] = i
visited = [False] * N
parent = [-1] * N
ret = []

def dfs(pre, cur):
	for nex in vec[cur]:
		if nex == pre or visited[nex]:
			continue
		visited[nex] = True
		dfs(cur, nex)
	if pre == -1 and diff[cur] == 1:
		return False
	if diff[cur] == 1:
		diff[cur] ^= 1
		diff[pre] ^= 1
		ret.append(convert[min(pre, cur), max(pre, cur)] + 1)
	return True
for i in range(N - 1):
	if visited[i]:
		continue
	visited[i] = True
	if not dfs(-1, i):
		print(-1)
		break
else:
	ret.sort()
	print(len(ret))
	print(*ret)


import sys
input = sys.stdin.readline
LLL = 1 << 20
(N, M) = map(int, input().split())
R = []
for _ in range(N):
	(a, b) = map(int, input().split())
	R.append((a * 2, b, 0))
for i in range(M):
	(l, r) = map(int, input().split())
	R.append((l * 2 - 1, 2, i))
	R.append((r * 2 + 1, 3, i))
R.sort(key=lambda x: x[0])
nodeid = 0
bf = -1
d = []
eid2lid = dict()
G = [set()]
for (x, f, i) in R:
	if f <= 1:
		d.append(int(f != bf and bf != -1))
		bf = f
		nodeid += 1
		G.append(set())
	else:
		if f == 3:
			lid = eid2lid[i]
			if nodeid != lid:
				G[nodeid].add((lid, i + 1))
				G[lid].add((nodeid, i + 1))
		eid2lid[i] = nodeid
d.append(int(bf == 1))
xxs = [-1] * (nodeid + 1)
g2 = [set() for _ in range(nodeid + 1)]
vs = set()
cut_edges = set()
for i in range(nodeid + 1):
	if i in vs:
		continue
	stack = [i]
	dfs_vs = []
	vs.add(i)
	while stack:
		v = stack.pop()
		dfs_vs.append(v)
		for (u, j) in G[v]:
			if u in vs:
				continue
			g2[v].add((u, j))
			stack.append(u)
			vs.add(u)
	for v in dfs_vs[::-1]:
		r = d[v]
		for (u, j) in g2[v]:
			ff = xxs[u]
			if ff:
				cut_edges.add(j)
			r = (r + ff) % 2
		xxs[v] = r if v != 0 else 0
	if xxs[i]:
		print(-1)
		break
else:
	print(len(cut_edges))
	print(*sorted(cut_edges))


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
	(a, b) = map(int, input().split())
	A[i] = a
	B[i] = b
S = sorted(A)
D = {a: i for (i, a) in enumerate(S)}
BB = [0] * (N + 1)
for i in range(N):
	BB[D[A[i]] + 1] = B[i]
for i in range(1, N + 1):
	BB[i - 1] ^= BB[i]

def bl(L, k):
	(l, r) = (-1, len(L))
	while r - l > 1:
		m = (l + r) // 2
		if L[m] >= k:
			r = m
		else:
			l = m
	return r
A = [D[a] for a in A]
X = [[] for _ in range(N + 1)]
DD = {}
for i in range(M):
	(l, r) = map(int, input().split())
	l = bl(S, l)
	r = bl(S, r + 1)
	X[l].append(r)
	X[r].append(l)
	DD[(l << 18) + r] = i
	DD[(r << 18) + l] = i
P = [-1] * (N + 1)
CH = [[] for _ in range(N + 1)]
R = []
done = [0] * (N + 1)
for ii in range(N + 1):
	Q = [ii]
	while Q:
		i = Q.pop()
		if P[i] < 0:
			R.append(i)
			done[i] = 1
		for j in X[i]:
			if P[j] >= 0:
				continue
			if j != P[i] and done[j] == 0:
				R.append(j)
				done[j] = 1
				P[j] = i
				CH[i].append(j)
				Q.append(j)
ANS = []
for i in R[1:][::-1]:
	if BB[i]:
		BB[i] ^= 1
		BB[P[i]] ^= 1
		if P[i] < 0:
			print(-1)
			exit()
		ANS.append(DD[(i << 18) + P[i]] + 1)
if sum(BB) == 0:
	print(len(ANS))
	print(*sorted(ANS))
else:
	print(-1)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(n, m) = LI()
co_to_ind = {}
A = []
B = []
for _ in range(n):
	(a, b) = LI()
	A += [a]
	B += [b]
S = sorted(A)
co_to_ind = {x: i for (i, x) in enumerate(S)}
X = [0] * (n + 1)
G = [[] for _ in range(n + 1)]
for i in range(n):
	X[co_to_ind[A[i]]] += B[i]
for i in range(n, 0, -1):
	X[i] ^= X[i - 1]
for i in range(m):
	(l, r) = LI()
	l = bisect_left(S, l)
	r = bisect_left(S, r + 1)
	G[l] += [(r, i)]
	G[r] += [(l, i)]
ans = []
visited = [0] * (n + 1)

def dfs(u):
	visited[u] = 1
	for (v, e) in G[u]:
		if visited[v]:
			continue
		dfs(v)
		if X[v]:
			ans.append(e + 1)
			X[u] ^= 1
for i in range(n + 1):
	if visited[i]:
		continue
	dfs(i)
	if X[i]:
		print(-1)
		exit()
ans.sort()
print(len(ans))
print(*ans)


import sys
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
import bisect

def run():
	(N, M) = map(int, sysread().split())
	AB = []
	for _ in range(N):
		AB.append(list(map(int, sysread().split())))
	AB = sorted(AB, key=lambda x: x[0])
	A = [a for (a, _) in AB]
	B = [0] + [b for (_, b) in AB] + [0]
	intB = [abs(B[idx] - B[idx - 1]) for idx in range(1, N + 2)]
	to = [[] for _ in range(N + 1)]
	for i in range(M):
		(l, r) = map(int, sysread().split())
		l = bisect.bisect_left(A, l)
		r = bisect.bisect_right(A, r)
		if l == r:
			continue
		to[l].append((i, r))
		to[r].append((i, l))
	seen = [False] * (N + 1)

	def dfs(node, to, stack):
		seen[node] = True
		stack.append(node)
		for (_, n_node) in to[node]:
			if not seen[n_node]:
				dfs(n_node, to, stack)
	trees = []
	for k in range(N + 1):
		tmp_stack = []
		if not seen[k]:
			dfs(k, to, tmp_stack)
			trees.append(tmp_stack)
			ret = 0
			for v in tmp_stack:
				ret += intB[v]
			if ret % 2 != 0:
				print(-1)
				return None
	seen2 = [False] * (N + 1)
	code_ids = []
	for tree in trees:
		while tree:
			cur = tree.pop()
			seen2[cur] = True
			for (id, next) in to[cur]:
				if not seen2[next]:
					if intB[cur] == 1:
						code_ids.append(id)
						intB[cur] = 0
						intB[next] = abs(intB[next] - 1)
					break
	print(len(code_ids))
	print(' '.join(list(map(str, sorted([h + 1 for h in code_ids])))))
run()


from bisect import bisect_left, bisect_right
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class UnionFind:

	def __init__(self, size):
		self.data = [-1] * size

	def find(self, x):
		if self.data[x] < 0:
			return x
		else:
			self.data[x] = self.find(self.data[x])
			return self.data[x]

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x != y:
			if self.data[y] < self.data[x]:
				(x, y) = (y, x)
			self.data[x] += self.data[y]
			self.data[y] = x
		return x != y

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.data[self.find(x)]
(N, M, *I) = map(int, open(0).read().split())
(AB, LR) = (I[:2 * N], I[2 * N:])
(A, B) = map(list, zip(*sorted(zip(*[iter(AB)] * 2))))
D = [l ^ r for (l, r) in zip([0] + B, B + [0])]
E = [set() for _ in range(N + 1)]
uf = UnionFind(N + 1)
for (i, (l, r)) in enumerate(zip(*[iter(LR)] * 2), 1):
	li = bisect_left(A, l)
	ri = bisect_right(A, r)
	if li == ri or uf.same(li, ri):
		continue
	uf.union(li, ri)
	E[li].add((ri, i))
	E[ri].add((li, i))
used = set()

def dfs(v, p):
	res = D[v]
	for (u, c) in E[v]:
		if u == p:
			continue
		ret = dfs(u, v)
		if ret == 1:
			used.add(c)
		D[u] = 0
		res ^= ret
	return res
for v in range(N + 1):
	if D[v]:
		D[v] = dfs(v, -1)
if all((d == 0 for d in D)):
	print(len(used))
	print(*sorted(used))
else:
	print(-1)


def main():
	import sys
	input = sys.stdin.readline
	from bisect import bisect_left, bisect_right
	sys.setrecursionlimit(10 ** 9)
	(N, M) = map(int, input().split())
	AB = []
	for i in [0] * N:
		(A, B) = map(int, input().split())
		AB.append((A, B))
	AB.sort(key=lambda x: x[0])
	POWER = 1
	x = [0] * (N + 1)
	x[0] = AB[0][POWER]
	for i in range(N - 1):
		x[i + 1] = AB[i][POWER] ^ AB[i + 1][POWER]
	x[N] = AB[N - 1][POWER]
	graph = [[] for _ in [0] * (N + 1)]
	for i in range(1, M + 1):
		(L, R) = map(int, input().split())
		L = bisect_left(AB, (L, 0))
		R = bisect_right(AB, (R, 1))
		graph[L].append((R, i))
		graph[R].append((L, i))
	ans = []
	POS = 0
	ID = 1

	def dfs(v):
		used[v] = True
		res = x[v]
		for edge in graph[v]:
			if used[edge[POS]]:
				continue
			r = dfs(edge[POS])
			if r:
				ans.append(edge[ID])
			res ^= r
		return res
	used = [False] * (N + 1)
	for i in range(N + 1):
		if used[i]:
			continue
		if dfs(i):
			print(-1)
			return
	print(len(ans))
	ans.sort()
	print(*ans)
main()


import sys
from bisect import *
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def dfs(u):
		fin[u] = True
		for (v, e) in to[u]:
			if fin[v]:
				continue
			dfs(v)
			if xx[v]:
				ans.append(e + 1)
				xx[u] ^= 1
	(n, m) = MI()
	ab = [LI() for _ in range(n)]
	lr = [LI() for _ in range(m)]
	aa = []
	bb = [0]
	for (a, b) in sorted(ab):
		aa.append(a)
		bb.append(b)
	bb.append(0)
	xx = [b0 ^ b1 for (b0, b1) in zip(bb, bb[1:])]
	lr = [(bisect_left(aa, l), bisect_right(aa, r)) for (l, r) in lr]
	to = defaultdict(list)
	for (i, (l, r)) in enumerate(lr):
		if l == r:
			continue
		to[l].append((r, i))
		to[r].append((l, i))
	ans = []
	fin = [False] * (n + 1)
	for i in range(n + 1):
		if fin[i]:
			continue
		dfs(i)
		if bb[i]:
			print(-1)
			exit()
	ans.sort()
	print(len(ans))
	print(*ans)
main()


def main():
	import sys
	from bisect import bisect_left
	from collections import deque
	input = sys.stdin.buffer.readline
	(N, M) = map(int, input().split())
	AB = [(0, 0)]
	for _ in range(N):
		(a, b) = map(int, input().split())
		AB.append((a, b))
	AB.append((10 ** 9 + 1, 0))
	AB.sort(key=lambda x: x[0])
	A = [AB[i][0] for i in range(N + 2)]
	P = [0] * (N + 2)
	for i in range(1, N + 2):
		if AB[i - 1][1] != AB[i][1]:
			P[i] = 1
	if sum(P) == 0:
		print(0)
		exit()
	adj = [[] for _ in range(N + 2)]
	E = {}
	for e in range(1, M + 1):
		(l, r) = map(int, input().split())
		i = bisect_left(A, l)
		j = bisect_left(A, r + 1)
		if i == j:
			continue
		adj[i].append(j)
		adj[j].append(i)
		E[i * (N + 3) + j] = e
		E[j * (N + 3) + i] = e
	for i in range(1, N + 2):
		if P[i] and len(adj[i]) == 0:
			print(-1)
			exit()
	seen = [0] * (N + 2)
	par = [0] * (N + 2)
	ans = []
	for v0 in range(1, N + 2):
		if seen[v0]:
			continue
		que = deque()
		que.append(v0)
		seen[v0] = 1
		seq = []
		while que:
			v = que.popleft()
			seq.append(v)
			for u in adj[v]:
				if seen[u] == 0:
					seen[u] = 1
					par[u] = v
					que.append(u)
		seq.reverse()
		for v in seq[:-1]:
			if P[v]:
				p = par[v]
				ans.append(E[v * (N + 3) + p])
				P[p] ^= 1
				P[v] = 0
	if sum(P):
		print(-1)
	else:
		ans.sort()
		print(len(ans))
		print(*ans)
main()


import sys
from collections import Counter
readline = sys.stdin.readline

class UF:

	def __init__(self, num):
		self.par = [-1] * num

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			stack = []
			while self.par[x] >= 0:
				stack.append(x)
				x = self.par[x]
			for xi in stack:
				self.par[xi] = x
			return x

	def union(self, x, y):
		rx = self.find(x)
		ry = self.find(y)
		if rx != ry:
			if self.par[rx] > self.par[ry]:
				(rx, ry) = (ry, rx)
			self.par[rx] += self.par[ry]
			self.par[ry] = rx
			return True
		else:
			return False
(N, M) = map(int, readline().split())
AB = [tuple(map(int, readline().split())) for _ in range(N)]
AB.sort()
(A, B) = map(list, zip(*AB))
Sw = [0] * N
push = 0
for i in range(N):
	Sw[i] = B[i] ^ push
	push ^= Sw[i]
Code = Counter()
Edge = []
for m in range(M):
	(l, r) = map(int, readline().split())
	r += 1
	ng = -1
	ok = N
	while abs(ok - ng) > 1:
		med = (ok + ng) // 2
		if l <= A[med]:
			ok = med
		else:
			ng = med
	L = ok
	ng = -1
	ok = N
	while abs(ok - ng) > 1:
		med = (ok + ng) // 2
		if r <= A[med]:
			ok = med
		else:
			ng = med
	R = ok
	if L == R:
		continue
	if L == N or R == 0:
		continue
	if (L, R) in Code:
		continue
	Edge.append((L, R))
	Code[L, R] = m + 1
	Code[R, L] = m + 1
UE = [[] for _ in range(N + 1)]
T = UF(N + 1)
for (l, r) in Edge:
	if T.union(l, r):
		UE[l].append(r)
		UE[r].append(l)
seen = set()
stack = []
for i in range(N, -1, -1):
	ri = T.find(i)
	if ri not in seen:
		stack.append(i)
		seen.add(ri)
used = set(stack)
Lord = []
par = [-1] * (N + 1)
while stack:
	vn = stack.pop()
	Lord.append(vn)
	for vf in UE[vn]:
		if vf not in used:
			used.add(vf)
			stack.append(vf)
			par[vf] = vn
Col = Sw[:] + [0]
anse = []
for l in Lord[::-1]:
	p = par[l]
	if p == -1:
		continue
	if Col[l]:
		Col[l] = 0
		Col[p] ^= 1
		anse.append(Code[l, p])
if any(Col[:-1]):
	print(-1)
else:
	anse.sort()
	print(len(anse))
	print(*anse)


import sys
input = sys.stdin.readline
from bisect import bisect_left as bl
(N, M) = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
	(a, b) = map(int, input().split())
	A[i] = a
	B[i] = b
S = sorted(A)
D = {a: i for (i, a) in enumerate(S)}
BB = [0] * (N + 1)
for i in range(N):
	BB[D[A[i]] + 1] = B[i]
for i in range(1, N + 1):
	BB[i - 1] ^= BB[i]
A = [D[a] for a in A]
X = [[] for _ in range(N + 1)]
DD = {}
for i in range(M):
	(l, r) = map(int, input().split())
	l = bl(S, l)
	r = bl(S, r + 1)
	X[l].append(r)
	X[r].append(l)
	DD[(l << 18) + r] = i
	DD[(r << 18) + l] = i
Q = [i for i in range(N + 1)]
P = [-1] * (N + 1)
R = []
while Q:
	i = Q.pop()
	if P[i] < 0:
		R.append(i)
	for j in X[i]:
		if P[j] >= 0:
			continue
		if j != P[i]:
			R.append(j)
			P[j] = i
			Q.append(j)
ANS = []
for i in R[1:][::-1]:
	if BB[i]:
		BB[i] ^= 1
		BB[P[i]] ^= 1
		if P[i] < 0:
			print(-1)
			break
		ANS.append(DD[(i << 18) + P[i]] + 1)
else:
	print(len(ANS))
	print(*sorted(ANS))


import sys
input = sys.stdin.readline
from operator import itemgetter
import bisect
(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
LR = [tuple(map(int, input().split())) for i in range(M)]
AB.sort(key=itemgetter(0))
A = [a for (a, b) in AB]
B = [0] + [b for (a, b) in AB] + [0]
C = []
for i in range(1, N + 2):
	C.append(B[i] ^ B[i - 1])
XY = []
for (l, r) in LR:
	XY.append((bisect.bisect_left(A, l), bisect.bisect_right(A, r)))
E = [[] for i in range(N + 1)]
for i in range(M):
	(x, y) = XY[i]
	if x == y:
		continue
	E[x].append((y, i + 1))
	E[y].append((x, i + 1))
BACK = [-1] * (N + 1)
NUM = [-1] * (N + 1)
ANS = []
for i in range(N + 1):
	if BACK[i] != -1:
		continue
	Q = [i]
	SORT = [i]
	BACK[i] = 0
	while Q:
		x = Q.pop()
		for (to, num) in E[x]:
			if BACK[to] == -1:
				SORT.append(to)
				Q.append(to)
				BACK[to] = x
				NUM[to] = num
	for x in SORT[1:][::-1]:
		if C[x] == 0:
			continue
		else:
			C[x] = 0
			C[BACK[x]] ^= 1
			ANS.append(NUM[x])
if max(C) == 1:
	print(-1)
else:
	print(len(ANS))
	print(*sorted(ANS))


import sys
from bisect import bisect_left, bisect
sys.setrecursionlimit(10 ** 5 + 5)

class UnionFind:

	def __init__(self, n):
		self.table = [-1] * n

	def _root(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self._root(self.table[x])
			return self.table[x]

	def find(self, x, y):
		return self._root(x) == self._root(y)

	def union(self, x, y):
		r1 = self._root(x)
		r2 = self._root(y)
		if r1 == r2:
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			self.table[r1] += d2
		else:
			self.table[r1] = r2
			self.table[r2] += d1

def solve(n, m, aaa, bbb, lll, rrr):
	(aaa, bbb) = map(list, zip(*sorted(zip(aaa, bbb))))
	b_diff = [bbb[0]] + [b0 ^ b1 for (b0, b1) in zip(bbb, bbb[1:])] + [bbb[-1]]
	cords = [set() for _ in range(n + 1)]
	uft = UnionFind(n + 1)
	for (i, (l, r)) in enumerate(zip(lll, rrr), start=1):
		li = bisect_left(aaa, l)
		ri = bisect(aaa, r)
		if li == ri or uft.find(li, ri):
			continue
		cords[li].add((ri, i))
		cords[ri].add((li, i))
		uft.union(li, ri)
	use_cords = set()

	def dfs(v, p):
		res = b_diff[v]
		for (u, cord) in cords[v]:
			if u == p:
				continue
			ret = dfs(u, v)
			if ret == 1:
				use_cords.add(cord)
			b_diff[u] = 0
			res ^= ret
		return res
	for v in range(n + 1):
		if b_diff[v]:
			b_diff[v] = dfs(v, -1)
	if sum(b_diff) == 0:
		print(len(use_cords))
		print(*sorted(use_cords))
	else:
		print(-1)
inp = list(map(int, sys.stdin.buffer.read().split()))
(n, m) = inp[:2]
aaa = inp[2:2 * n + 2:2]
bbb = inp[3:2 * n + 2:2]
lll = inp[2 * n + 2::2]
rrr = inp[2 * n + 3::2]
solve(n, m, aaa, bbb, lll, rrr)