分数: 700 点
问题陈述
给你二进制字符串 A = A_1 A_2 \ldots A_N 和 B = B_1 B_2 \ldots B_N 长度 N.
您可以执行 M 操作类型。的 i-th类型的操作由一对整数表示 (x_i, y_i) 与 1 \le x_i, y_i \le N,它翻转了 A_{y_i} 当 A_{x_i} = 1。有可能的是 x_i = y_i。在这里,翻转意味着改变 0 to 1 or 1 to 0.
判断是否可以转换 A 转换为字符串等于 B 最多执行 2N 操作 A,如果是,则构造一种这样的方式。
你被给予 T 测试用例;逐一解决。
约束
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- A 和 B 是长度的二进制字符串 N.
- A \neq B
- 1 \le x_i \le N (1 \le i \le M)
- 1 \le y_i \le N (1 \le i \le M)
- 总和 N 和 M 所有测试用例最多 2 \times 10^5.
- T, N, M, x_i, y_i 是整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N A B M x_1 y_1 x_2 y_2 \vdots x_M y_M
输出
的输出 T 测试用例按顺序排列。
对于每个测试用例,输出如下。
如果不存在满足条件的操作序列,则输出 -1 在一行上。
如果存在满足条件的操作序列,令 K 是操作序列的长度并且 C_i 是索引 执行 i第次操作,输出如下:
K C_1 C_2 \ldots C_K
在这里, K 最多必须是 2N,以及操作 i 不得在以下情况下执行 A_{x_i} = 0.
示例输入 1
3 4 0100 1010 4 1 2 2 1 2 3 4 3 2 10 01 1 1 2 2 01 00 3 1 1 1 2 2 1
示例输出 1
3 2 3 1 -1 3 3 2 1
对于第一个测试用例,您可以执行如下操作。
- 最初, A = 0100.
- 执行操作 2。现在, A = 1100.
- 执行操作 3。现在, A = 1110.
- 执行操作 1。现在, A = 1010.
对于第二个测试用例,无论执行什么操作,都不可能使 A_1 等于 0.
请注意,与第三个测试用例一样, x_i = y_i 是可能的。