AT_arc207_e.[ARC207E] Erase and Append

给定长度为 $N$ 的仅由 0 和 1 组成的字符串 $s$ 和 $t$。你需要判断是否可以通过下述操作至少 $0$ 次且最多 $N+1$ 次，将 $s$ 变为 $t$，并在可能的情况下给出一种操作序列。

操作：依次执行以下步骤。

1. 选择满足 $1 \le a, b \le N$ 且 $|a - b| = 1$ 的整数 $a$ 和 $b$。
2. 将 $s$ 的第 $a$ 个字符（从左到右）追加到 $s$ 的末尾。
3. 从 $s$ 的开头移除第 $b$ 个字符，并保持剩余字符的原有顺序。

给定 $T$ 组测试数据，对于每组测试数据，判断能否通过上述操作将 $s$ 变为 $t$。

输入从标准输入获取，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每组测试数据格式如下：

$N$ $s$ $t$

按输入顺序输出每组测试数据的答案。若无法通过至多 $N+1$ 次操作将 $s$ 变为 $t$，则输出 -1。若可以实现，先输出操作次数 $K$，随后 $K$ 行每行两个空格分隔的整数 $a_j$ 和 $b_j$，表示第 $j$ 步操作选择的 $a$ 和 $b$。

样例解释 1

第一组数据中，$s$ 为 00101，$t$ 为 00010。

• 选择 $a=2$ 和 $b=3$，将第 $2$ 个字符 0 追加到末尾，再移除第 $3$ 个字符，可以将 $s$ 变为 $t$。
• 注意：每次操作选择的 $a$ 和 $b$ 必须满足 $|a-b|=1$。

第二组数据中，$s$ 和 $t$ 已经相同，无需任何操作。

第三组数据中，不论如何操作，都无法将 $s$ 变为 $t$。

数据范围

• $1 \le T \le 10^{5}$
• $2 \le N \le 2 \times 10^{5}$
• $s$ 和 $t$ 是长度为 $N$ 的仅包含 0 和 1 的字符串。
• 所有测试数据中 $N$ 的总和不超过 $2 \times 10^{5}$。

由 ChatGPT 5 翻译