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.

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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()

decomp = list(seen)
decomp.sort()
node_num = len(decomp)
comp = dict()
for i, item in enumerate(decomp):
    comp[item] = i

# Take diff
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(decomp, l)
    rgt = bisect.bisect_right(decomp, 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)
    # Check last node is ok or not
    if ret == 1:
        print(-1)
        return

# Check trees cover all 1 or not
for c, is_visited in zip(d, visited):
    if not is_visited and c:
        print(-1)
        return

ans.sort()
print(len(ans))
print(*ans)

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
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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])
    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()

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 = [B[0]] + [l ^ r for l, r in zip(B, B[1:])] + [B[-1]]
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 sum(D) == 0:
    print(len(used))
    print(*sorted(used))
else:
    print(-1)

#!/usr/bin/env python3
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
# print("d", d)

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
# print("lr", lr)

edge = [[] for _ in range(node_num + 1)]
for l, r in lr:
    edge[l].append(r)
    edge[r].append(l)
# print("edge", edge)

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)
    # Check last node is ok or not
    if ret == 1:
        print(-1)
        return

# Check trees cover all 1 or not
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 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)

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)