并联的险境

题目描述

由于 AlDebaran 王国的入侵,AtCoder 王国的各地被安放了炸弹。

幸运的是,由于 AtCoder 王国 ABC 队的奋战,你得到了一部分控制装置,决定用它们尝试解除炸弹。

被安放的炸弹共有 $N$ 个,编号为 $1$ 到 $N$。炸弹 $i$ 位于坐标 $A_i$,其电源在 $B_i=1$ 时开启,在 $B_i=0$ 时关闭。

控制装置有 $M$ 根电线,编号为 $1$ 到 $M$。切断电线 $j$ 时,坐标在 $L_j$ 以上 $R_j$ 以下的所有炸弹的电源会被切换(开变关、关变开)。

请判断能否通过选择合适的电线来切断,使所有炸弹的电源都关闭;如果可以,请输出一种这样的电线组合。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_1$ $B_1$
: $A_N$ $B_N$
$L_1$ $R_1$
: $L_M$ $R_M$

输出格式

如果无法使所有炸弹的电源关闭,则输出 -1。如果可能,按如下格式输出一种达成该目标的电线组合:

$k$
$c_1$ $c_2$ $\dots$ $c_k$

其中,$k$ 是切断的电线数(可以为 $0$)。

另外,$c_1, c_2, \dots, c_k$ 是被切断的电线编号,必须满足 $1 \leq c_1 \lt c_2 \lt \dots \lt c_k \leq M$。

样例

3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9

2
1 4

坐标 $5, 10$ 有电源开启的炸弹,坐标 $8$ 有电源关闭的炸弹。

切断电线 $1$ 后,坐标在 $1$ 以上 $10$ 以下的炸弹,也就是所有炸弹的电源都会被切换。

切断电线 $4$ 后,坐标在 $8$ 以上 $9$ 以下的炸弹,也就是只有炸弹 $3$ 的电源会被切换。

因此,切断电线 $1, 4$ 这 $2$ 根,即可使所有炸弹的电源关闭。

4 2
2 0
3 1
5 1
7 0
1 4
4 7

-1

无论怎么选择切断的电线,都无法使所有炸弹的电源关闭。

3 2
5 0
10 0
8 0
6 9
66 99

0

一开始所有炸弹的电源就已经关闭,所以不需要切断电线。

12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235

5
1 7 8 9 11

可能存在多种满足条件的电线组合,输出其中任意一种即可。

数据范围

• 输入均为整数
• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9\ (1 \leq i \leq N)$
• $A_i$ 互不相同
• $B_i$ 是 $0$ 或 $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)$

提示

答案不唯一,输出任意合法解即可。