← 返回题目列表

AtCoder · abc155_f

F. 并行的危险

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

被阿尔德巴兰王国入侵后,我们的国家AtCoder王国各地都安放了炸弹。

幸运的是,我们的军事小组 ABC 已经成功获得了一个装置,它是控制炸弹的系统的一部分。

有 N 炸弹,编号 1 to N,在我国种植。炸弹 i 被种植在坐标处 A_i。当前如果满足以下条件则已激活 B_i=1,并在以下情况下停用 B_i=0.

该设备有 M 编号为 1 to M。如果我们剪断绳子 j,坐标之间所有放置的炸弹的状态 L_j 和 R_j (含)将被切换 - 从激活到停用,反之亦然。

确定是否可以同时停用所有炸弹。如果答案是肯定的,则输出一组应该被切断的电线。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9\ (1 \leq i \leq N)
  • A_i 成对不同。
  • 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)

输入

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

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 < c_2 < \dots < c_k \leq M 必须保留。


示例输入 1

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

示例输出 1

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

示例输出 2

-1

切断任何一组电线不会同时停用所有炸弹。


示例输入 3

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

示例输出 3

0

所有炸弹都已经失效,所以我们不需要切断任何电线。


示例输入 4

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

示例输出 4

5
1 7 8 9 11

如果有多组绳索在被切断时使所有炸弹失效,则可以打印其中任何一组。