#ABC155F. Perils in Parallel

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 NN bombs, numbered 11 to NN, planted in our country. Bomb ii is planted at the coordinate AiA_i. It is currently activated if Bi=1B_i=1, and deactivated if Bi=0B_i=0.

The device has MM cords numbered 11 to MM. If we cut Cord jj, the states of all the bombs planted between the coordinates LjL_j and RjR_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.

在被德巴兰王国入侵后,我们的国家 AtCoder Kingdom 全境都被安放了炸弹。

幸运的是,我们名为 ABC 的军事小组设法获得了一个装置,它是控制炸弹系统的一部分。

我国境内共有 NN 枚炸弹,编号为 11NN 。炸弹 ii 安装在坐标 AiA_i 处。如果 Bi=1B_i=1 激活, Bi=0B_i=0 则解除。

该装置有 MM 根电线,编号为 11MM 。如果我们切断 jj 号线,那么在坐标 LjL_jRjR_j (含)之间放置的所有炸弹的状态都将发生转换--从激活状态变为停用状态,反之亦然。

判断是否有可能同时解除所有炸弹。如果答案是肯定的,则输出一组应剪断的线缆。

输入格式

输入内容按以下格式标准输入:

NN MM
A1A_1 B1B_1
::
ANA_N BNB_N
L1L_1 R1R_1
::
LML_M RMR_M

输出格式

如果无法同时拆除所有炸弹,则打印 -1。如果可以做到,则打印一组应剪断的绳索,如下所示:

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

这里, kk 是绳索的数量(可能是 00 ), c1,c2,,ckc_1, c_2, \dots, c_k 代表应剪断的绳索。 1c1<c2<<ckM1 \leq c_1 \lt c_2 \lt \dots \lt c_k \leq M 必须保持。

样例 #1

样例输入 #1

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

样例输出 #1

2
1 4

样例 #2

样例输入 #2

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

样例输出 #2

-1

样例 #3

样例输入 #3

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

样例输出 #3

0

样例 #4

样例输入 #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

说明

数据规模与约定

  • 所有输入值均为整数。
  • 1N1051 \leq N \leq 10^5
  • 1Ai109 (1iN)1 \leq A_i \leq 10^9\ (1 \leq i \leq N)
  • AiA_i 是成对的不同值。
  • BiB_i0011(1iN)(1 \leq i \leq N)
  • 1M2×1051 \leq M \leq 2 \times 10^5
  • 1LjRj109 (1jM)1 \leq L_j \leq R_j \leq 10^9\ (1 \leq j \leq M)

样例 11 解释

在坐标 5,105, 10 处有两个已激活的炸弹,在坐标 88 处有一个未激活的炸弹。

切断 11 线可以切换坐标 111010 之间所有炸弹的状态,也就是切换所有三个炸弹的状态。

割线 44 切换了坐标 8899 之间所有炸弹的状态,也就是炸弹 33 的状态。

因此,我们可以通过剪断 1144 来解除所有炸弹。

样例 22 解释

切断任何一组绳索都不会同时解除所有炸弹。

样例 33 解释

所有炸弹都已停用,因此我们不需要剪断任何线缆。

样例 44 解释

如果有多组绳索,剪断后所有炸弹都会失效,则可以打印其中任何一组。