Everool 有一个长度为 $$$2n$$$ 的二进制字符串 $$$s$$$。请注意,二进制字符串是仅由字符 $$$0$$$ 和 $$$1$$$ 组成的字符串。他想将 $$$s$$$ 划分为两个不相交的相等子序列。他需要你的帮助才能做到这一点。
您只能执行以下操作一次。
- 您可以选择 $$$s$$$ 的任何子序列(可能为空)并将其向右旋转一位。
换句话说,您可以选择索引序列 $$$b_1, b_2, \ldots, b_m$$$,其中 $$$1 \le b_1 < b_2 < \ldots < b_m \le 2n$$$。之后,您同时设置 $$$$$$s_{b_1} := s_{b_m},$$$$$$ $$$$$$s_{b_2} := s_{b_1},$$$$$$ $$$$$$\ldots,$$$$$$ $$$$$$s_{b_m} := s_{b_{m-1}}.$$$$$$
在执行一次允许的操作后,您能否将 $$$s$$$ 划分为两个不相交的相等子序列?
将 $$$s$$$ 划分为两个不相交的相等子序列 $$$s^p$$$ 和 $$$s^q$$$ 是两个索引递增数组 $$$p_1, p_2, \ldots, p_n$$$ 和 $$$q_1, q_2, \ldots, q_n$$$,这样从 $$$1$$$ 到 $$$1$$$ 的每个整数$$$2n$$$ 在 $$$p$$$ 或 $$$q$$$ 中只出现一次,$$$s^p = s_{p_1} s_{p_2} \ldots s_{p_n}$$$、$$$s^q = s_{q_1} s_{q_2} \ldots s_{q_n}$$$ 和 $$$s^p = s^q$$$。
如果执行任何类型的操作后都无法分区,则报告 $$$-1$$$。
如果可以进行操作并将 $$$s$$$ 划分为两个不相交的子序列 $$$s^p$$$ 和 $$$s^q$$$,使得 $$$s^p = s^q$$$,则打印 $$$b$$$ 的元素和 $$$s^p$$$ 的索引,i。 e.值 $$$p_1、p_2、\ldots、p_n$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),其中 $$$2n$$$ 是二进制字符串的长度。
每个测试用例的第二行包含长度为$$$2n$$$的二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,请遵循以下输出格式。
如果无解,则打印$$$-1$$$。
否则,
- 在第一行中,打印一个整数 $$$m$$$ ($$$0 \leq m \leq 2n$$$),后跟 $$$m$$$ 不同索引 $$$b_1$$$、$$$b_2$$$、...、$$$b_m$$$(按升序排列)。
- 在第二行中,打印 $$$n$$$ 不同索引 $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ (按升序排列)。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
4 2 1010 3 100010 2 1111 2 1110
输出 #1
0 1 2 2 3 5 1 2 5 3 2 3 4 1 4 -1
注意
在第一个测试用例中,$$$b$$$ 为空。所以字符串 $$$s$$$ 没有改变。现在$$$s^p = s_1 s_2 = \mathtt{10}$$$,$$$s^q = s_3s_4 = \mathtt{10}$$$。
在第二个测试用例中,$$$b=[3,5]$$$。最初是$$$s_3=\mathtt{0}$$$,$$$s_5=\mathtt{1}$$$。在执行操作时,我们同时设置$$$s_3=\mathtt{1}$$$和$$$s_5=\mathtt{0}$$$。
因此,执行操作时 $$$s$$$ 会更新为 101000。
现在,如果我们在 $$$s^p$$$ 中的索引 $$$[1,2,5]$$$ 处获取字符,我们会得到 $$$s_1=\mathtt{100}$$$。索引 $$$[3,4,6]$$$ 处的字符也在 $$$s^q$$$ 中。因此$$$s^q=100$$$。我们就完成了$$$s^p=s^q$$$。
在第四个测试用例中,可以证明在执行任何操作后都不可能对字符串进行分区。