F - 并行危险

因为SPJ的问题，请去https://atcoder.jp/contests/abc155/tasks/abc155_f 提交

评分：600分

问题描述

在被AlDebaran王国入侵后，炸弹遍布在我们的国家AtCoder王国中。然而，我们的军事团队ABC设法获取了一部分控制炸弹的设备。

在我们国家中有N颗炸弹，编号为1到N，其中第i个炸弹位于坐标$A_i$上。如果$B_i=1$，则它处于激活状态；如果$B_i=0$，则它处于非激活状态。

设备上有$M$条线，编号为$1$到$M$。如果我们切断第$j$条线，则从坐标$L_j$到$R_j$的所有炸弹的状态将被转换，从激活状态转换到非激活状态，或者从非激活状态转换到激活状态。

确定是否有可能同时关闭所有炸弹。如果答案是肯定的，则输出应该切断的一组线。

约束条件

• 所有输入的值都是整数。
• $1≤N≤10^5$
• $1≤A_i≤10^9 (1≤i≤N)$
• $A_i$两两不同。
• $B_i$为$0$或$1$。 $(1≤i≤N)$
• $1≤M≤2×10^5$
• $1≤L_j≤R_j≤10^9 (1≤j≤M)$

输入

输入通过标准输入给出，格式如下：

$N$ $M$

$A_1$ $B_1$

:

$A_N$ $B_N$

$L_1$ $R_1$

:

$L_M$ $R_M$

输出

如果不可能同时关闭所有炸弹，则输出-1。如果有可能，则按以下格式输出一组应该剪断的线：

k
c1 c2... ck

其中，$k$是线的数量（可能为$0$），$c_1$, $c_2$, ..., $c_k$表示应该剪断的线。必须满足$1≤c1,c2...ck≤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之间的炸弹的状态，也就是第三颗炸弹的状态。 因此，切掉线1和线4即可同时关闭所有炸弹。

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

如果有多组线剪断后可以同时关闭所有炸弹，可以输出其中的任何一组。