AT_arc215_e.[ARC215E] CNOT Party

给定两个长度为 $N$ 的二进制字符串 $A = A_1 A_2 \ldots A_N$ 和 $B = B_1 B_2 \ldots B_N$。

你可以进行 $M$ 种不同类型的操作。第 $i$ 种操作由一对整数 $(x_i, y_i)$ 表示，$1 \le x_i, y_i \le N$。当 $A_{x_i} = 1$ 时，该操作会将 $A_{y_i}$ 的值翻转（$0$ 变为 $1$，$1$ 变为 $0$）。允许 $x_i = y_i$。这里“翻转”是指将 $0$ 变为 $1$，将 $1$ 变为 $0$。

请判断是否有办法最多通过 $2N$ 次上述操作，将 $A$ 变为与 $B$ 完全相同的字符串。如果可以，请构造出一种可行方案。

共有 $T$ 组测试数据，请分别解决每一组。

输入由标准输入给出，格式如下：

$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_1, C_2, \ldots, C_K$ 种操作，则输出：

$K$ $C_1$ $C_2$ $\ldots$ $C_K$

其中 $K$ 不超过 $2N$，且在进行第 $i$ 次操作时，不能使 $A_{x_i}=0$。

样例解释 1

对于第一组测试，操作如下：

• 初始 $A = 0100$。
• 执行第 $2$ 次操作，$A = 1100$。
• 执行第 $3$ 次操作，$A = 1110$。
• 执行第 $1$ 次操作，$A = 1010$。

对于第二组测试，无论如何操作，也无法使 $A_1$ 变为 $0$。

注意，如第三组测试所示，允许 $x_i = y_i$。

约束条件

• $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$ 均为整数。

由 ChatGPT 5 翻译