您有两个字符串 $$$a$$$ 和 $$$b$$$,偶数长度 $$$n$$$ 由字符 0 和 1 组成。
我们现在正处于最后阶段。为了最终使宇宙完美平衡,您需要使字符串 $$$a$$$ 和 $$$b$$$ 相等。
一步中,您可以选择任意长度为偶数的 $$$a$$$ 前缀并将其反转。形式上,如果 $$$a = a_1 a_2 \ldots a_n$$$,您可以选择正偶数 $$$p \le n$$$ 并将 $$$a$$$ 设置为 $$$a_p a_{p-1} \ldots a_1 a_{p+1} a_{p+2} \ldots a_n$$$。
找到一种方法,使用至多 $$$n + 1$$$ 上述类型的反转,使 $$$a$$$ 等于 $$$b$$$,或者确定这种方法不存在。不必最小化反转次数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$),表示测试用例的数量。
每个测试用例由两行组成。第一行包含长度为 $$$n$$$ 的字符串 $$$a$$$,第二行包含相同长度的字符串 $$$b$$$ ($$$2 \le n \le 4000$$$; $$$n \bmod 2 = 0$$$)。两个字符串均由字符 0 和 1 组成。
所有 $$$t$$$ 测试用例的 $$$n$$$ 总和不超过 $$$4000$$$。
输出
对于每个测试用例,如果在最多 $$$n + 1$$$ 反转中不可能使 $$$a$$$ 等于 $$$b$$$,则输出单个整数 $$$-1$$$。
否则,输出一个整数 $$$k$$$ ($$$0 \le k \le n + 1$$$),表示步骤序列中的反转次数,后跟 $$$k$$$ 偶数整数 $$$p_1, p_2, \ldots, p_k$$$ ($$$2 \le p_i \le n$$$; $$$p_i \bmod 2 = 0$$$),表示要反转的$$$a$$$的前缀长度,按时间顺序排列。
请注意,$$$k$$$ 不必最小化。如果有多个解,则输出任意一个。
示例
输入 #1
4 0100011011 1101011000 10101010 10101010 0011 1001 100011 110010
输出 #1
3 6 4 10 0 -1 7 2 6 2 6 2 2 6
注意
在第一个测试用例中,字符串 $$$a$$$ 更改如下:
- 第一次反转后:1000101011;
- 第二次反转后:0001101011;
- 第三次反转后:1101011000。