← 返回题目列表

Codeforces · 2158/D

D. 回文翻转

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

给定两个二进制字符串 $$$s$$$ 和 $$$t$$$,每个字符串的长度 $$$n$$$ 相同。您可以执行以下操作:

  • 选择索引 $$$l$$$, $$$r$$$ ($$$1 \le \color{red}{l \lt r} \le n$$$) 使得子串 $$$s_{l,r}$$$ 是回文并翻转子串 $$$s_{l,r}$$$ 中的所有位。

目标是最终使 $$$s$$$ 等于 $$$t$$$,执行上述任何操作最多 $$$2n$$$ 次(可能没有)。

字符串 $$$s$$$ 的子字符串 $$$s_{l,r}$$$ 是从索引 $$$l$$$ 开始到索引 $$$r$$$ 结束的连续字符序列(包括两者),其中 $$$1 \leq l \lt r \leq |s|$$$。这里$$$|s|$$$表示字符串$$$s$$$的长度。

如果一个字符串向前和向后读取相同,则该字符串是回文。例如,字符串 101 和 00 是回文,而 10 不是。

翻转子串中的所有位意味着更改每个位 0 to 1 和每个 该子字符串中的 1 to 0 。例如,翻转子串 101 结果 010.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,如果不可能达到目标,则打印$$$-1$$$。

否则,第一行应包含一个整数 $$$k$$$ ($$$0 \leq k \leq 2n$$$) — 操作数。

对于接下来的 $$$k$$$ 行,打印两个整数 $$$l, r$$$ ($$$1 \leq l \lt r \leq n$$$) - 您在每个操作中选择的索引。请注意,$$$s_{l,r}$$$ 在这个阶段必须是回文。

示例

输入
复制

3
5
01011
10000
7
1010101
0101010
4
0010
0010

输出
复制

2
1 3
3 5
1
1 7
0

注意

对于第一个测试用例:

  • 最初,$$$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$$$。无需任何操作。