CF2158D.Palindrome Flipping

You are given two binary strings $s$ and $t$, each of the same length $n$. You are allowed to perform the following operation:

• Pick indices $l$, $r$ ($1 \le \color{red}{l \lt r} \le n$) such that substring $s_{l,r}$ is a palindrome and flip all bits in substring $s_{l,r}$.

The goal is to finally make $s$ equal to $t$, performing any of the above operations at most $2n$ times (possibly none).

A substring $s_{l,r}$ of a string $s$ is the contiguous sequence of characters starting from index $l$ and ending at index $r$ (both inclusive), where $1 \leq l \lt r \leq |s|$. Here $|s|$ denotes the length of the string $s$.

A string is a palindrome if it reads the same forwards and backwards. For example, the strings 101 and 00 are palindromes, while 10 is not.

Flipping all bits in a substring means changing each 0 to 1 and each 1 to 0 in that substring. For example, flipping the substring 101 results in 010.

给你两个长度均为 $n$ 的二进制字符串 $s$ 和 $t$。你可以执行以下操作：

• 选择下标 $l$、$r$（满足 $1 \le \color{red}{l \lt r} \le n$），使得子串 $s_{l,r}$ 是一个回文串，并将子串 $s_{l,r}$ 中的所有位取反。

目标是通过至多 $2n$ 次（可以为零次）上述操作，使 $s$ 最终等于 $t$。

字符串 $s$ 的子串 $s_{l,r}$ 是指从下标 $l$ 开始、到下标 $r$ 结束（均包含）的连续字符序列，其中 $1 \leq l \lt r \leq |s|$。这里 $|s|$ 表示字符串 $s$ 的长度。

若一个字符串正读与反读完全相同，则称其为回文串。例如，字符串 101 和 00 是回文串，而 10 不是。

对子串中所有位取反，是指将该子串中的每个 0 变为 1，每个 1 变为 0。例如，对子串 101 取反后得到 010。

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 5\cdot 10^3$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($4 \le n \le 100$) — the length of the strings $s$ and $t$.

The next two lines of each test case contain the binary strings $s$ and $t$, respectively.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$（$1 \le T \le 5\cdot 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$4 \le n \le 100$）—— 字符串 $s$ 和 $t$ 的长度。

每个测试用例的接下来两行分别包含二进制字符串 $s$ 和 $t$。

保证所有测试用例的 $n^2$ 之和不超过 $5\cdot 10^5$。

For each test case, if it is impossible to achieve the goal, print $-1$.

Otherwise, the first line should contain an integer $k$ ($0 \leq k \leq 2n$) — the number of operations.

For each of the next $k$ lines, print two integers $l, r$ ($1 \leq l \lt r \leq n$) — the indices you choose in each operation. Note that $s_{l,r}$ must be a palindrome at this stage.

对于每个测试用例，如果无法达成目标，则输出 $-1$。

否则，第一行应包含一个整数 $k$（$0 \leq k \leq 2n$）—— 表示操作次数。

接下来的 $k$ 行中，每行输出两个整数 $l, r$（$1 \leq l \lt r \leq n$）—— 表示每次操作所选择的下标。注意：此时子串 $s_{l,r}$ 必须是一个回文串。

For the first test case:

• Initially, $s = \mathtt{01011}$ and $t = \mathtt{10000}$.
• First, we choose $l=1$ and $r=3$. This is a valid operation since $s_{1,3} = \mathtt{010}$ is a palindrome. After flipping $s_{1,3}$, $s = \mathtt{10111}$.
• Then, we choose $l=3$ and $r=5$. This is a valid operation since $s_{3,5} = \mathtt{111}$ is a palindrome. After flipping $s_{3,5}$, $s = \mathtt{10000}$.
• Now, $s$ is equal to $t$.

For the second test case:

• Initially, $s = \mathtt{1010101}$ and $t = \mathtt{0101010}$.
• First, we choose $l=1$ and $r=7$. This is a valid operation since $s_{1,7} = \mathtt{1010101}$ is a palindrome. After flipping $s_{1,7}$, $s = \mathtt{0101010}$.
• Now, $s$ is equal to $t$.

For the third test case:

• Initially, $s$ is equal to $t$. No operations are needed.

对于第一个测试用例：

• 初始时，$s = \mathtt{01011}$ 且 $t = \mathtt{10000}$。
• 首先，我们选择 $l=1$ 和 $r=3$。该操作合法，因为子串 $s_{1,3} = \mathtt{010}$ 是一个回文串。翻转 $s_{1,3}$ 后，$s = \mathtt{10111}$。
• 接着，我们选择 $l=3$ 和 $r=5$。该操作合法，因为子串 $s_{3,5} = \mathtt{111}$ 是一个回文串。翻转 $s_{3,5}$ 后，$s = \mathtt{10000}$。
• 此时，$s$ 已等于 $t$。

对于第二个测试用例：

• 初始时，$s = \mathtt{1010101}$ 且 $t = \mathtt{0101010}$。
• 首先，我们选择 $l=1$ 和 $r=7$。该操作合法，因为子串 $s_{1,7} = \mathtt{1010101}$ 是一个回文串。翻转 $s_{1,7}$ 后，$s = \mathtt{0101010}$。
• 此时，$s$ 已等于 $t$。

对于第三个测试用例：

• 初始时，$s$ 已等于 $t$。无需任何操作。