AT_abc155_f.[ABC155F] Perils in Parallel

由于 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$

$\vdots$

$A_N$ $B_N$

$L_1$ $R_1$

$\vdots$

$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\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)$

样例解释 1

坐标 $5,\ 10$ 的炸弹电源为开启，坐标 $8$ 的炸弹电源为关闭。切断导线 $1$ 时，坐标在 $1$ 到 $10$ 之间的所有炸弹（即全部炸弹）电源会切换。切断导线 $4$ 时，坐标在 $8$ 到 $9$ 之间的炸弹（即炸弹 $3$）电源会切换。因此，切断导线 $1$ 和 $4$ 共 $2$ 根，可以使所有炸弹电源关闭。

样例解释 2

无论如何选择切断的导线，都无法使所有炸弹电源关闭。

样例解释 3

一开始所有炸弹电源均为关闭，因此无需切断任何导线。

样例解释 4

如果存在多组满足条件的导线组合，输出任意一组均可。

由 ChatGPT 4.1 翻译