← 返回题目列表

AtCoder · arc215_e

E. CNOT党

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

分数: 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 是可能的。