CF2158D Palindrome Flipping

给定两个长度均为 $n$ 的 $01$ 串 $s$ 和 $t$。你可以进行如下操作： - 选择下标 $l,r\,(1 \leq {\color{red}{l < r}} \leq n)$，使得子串 $s_{l,r}$ 是回文串，并将该子串内所有位反转。 目标是通过上述操作最多 $2n$ 次（可以为零次）后，使得 $s$ 与 $t$ 相等。 字符串 $s$ 的子串 $s_{l,r}$ 指的是 $s$ 第 $l$ 位到第 $r$ 位（含端点）的连续字符子序列，其中 $1 \leq l < r \leq |s|$。这里 $|s|$ 表示字符串 $s$ 的长度。 回文串是指正着和反着读都一样的字符串。例如，$\texttt{101}$ 和 $\texttt{00}$ 是回文串，而 $\texttt{10}$ 不是。 反转子串的所有位，意为把 $\texttt{0}$ 变为 $\texttt{1}$，$\texttt{1}$ 变为 $\texttt{0}$。例如，反转 $\texttt{101}$ 得到 $\texttt{010}$。

每个测试点包含多个测试用例。第一行为用例数 $T$（$1 \leq T \leq 5\cdot 10^3$）。接下来是每个用例的描述。 每个用例第一行为一个整数 $n$（$4 \leq n \leq 100$），表示字符串 $s$ 和 $t$ 的长度。 接下来两行分别为二进制字符串 $s$ 和 $t$。 保证所有用例的 $n^2$ 之和不超过 $5\cdot 10^5$。

对于每组测试数据，如果无法完成目标，输出 $-1$。 否则，第一行输出一个整数 $k$（$0 \leq k \leq 2n$），表示操作次数。 接下来的 $k$ 行，每行输出两个整数 $l, r$（$1 \leq l < r \leq n$），表示每次操作时选取的下标。注意，在每次操作时，$s_{l,r}$ 必须是当时的回文串。

对于第一个用例： - 初始 $s = \mathtt{01011}$，$t = \mathtt{10000}$。 - 第一步，选择 $l=1$，$r=3$，$s_{1,3}=\mathtt{010}$ 是回文串。翻转后 $s=\mathtt{10111}$。 - 第二步，选择 $l=3$，$r=5$，$s_{3,5}=\mathtt{111}$ 是回文串。翻转后 $s=\mathtt{10000}$。 - 此时 $s$ 等于 $t$。 对于第二个用例： - 初始 $s = \mathtt{1010101}$，$t = \mathtt{0101010}$。 - 第一步，选择 $l=1$，$r=7$，$s_{1,7}=\mathtt{1010101}$ 是回文串。翻转后 $s=\mathtt{0101010}$。 - 此时 $s$ 等于 $t$。 第三个用例： - 初始时 $s$ 就已经等于 $t$，无需进行任何操作。 由 ChatGPT 5 翻译