给定两个二进制字符串 $$$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}$$$ 在这个阶段必须是回文。
示例
输入复制
350101110000710101010101010400100010
输出复制
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$$$。无需任何操作。