CF1736D.Equal Binary Subsequences

Everool has a binary string $s$ of length $2n$. Note that a binary string is a string consisting of only characters $0$ and $1$. He wants to partition $s$ into two disjoint equal subsequences. He needs your help to do it.

You are allowed to do the following operation exactly once.

• You can choose any subsequence (possibly empty) of $s$ and rotate it right by one position.

In other words, you can select a sequence of indices $b_1, b_2, \ldots, b_m$, where $1 \le b_1 \lt b_2 \lt \ldots \lt b_m \le 2n$. After that you simultaneously set $$s_{b_1} := s_{b_m},$$ $$s_{b_2} := s_{b_1},$$ $$\ldots,$$ $$s_{b_m} := s_{b_{m-1}}.$$

Can you partition $s$ into two disjoint equal subsequences after performing the allowed operation exactly once?

A partition of $s$ into two disjoint equal subsequences $s^p$ and $s^q$ is two increasing arrays of indices $p_1, p_2, \ldots, p_n$ and $q_1, q_2, \ldots, q_n$, such that each integer from $1$ to $2n$ is encountered in either $p$ or $q$ exactly once, $s^p = s_{p_1} s_{p_2} \ldots s_{p_n}$, $s^q = s_{q_1} s_{q_2} \ldots s_{q_n}$, and $s^p = s^q$.

If it is not possible to partition after performing any kind of operation, report $-1$.

If it is possible to do the operation and partition $s$ into two disjoint subsequences $s^p$ and $s^q$, such that $s^p = s^q$, print elements of $b$ and indices of $s^p$, i. e. the values $p_1, p_2, \ldots, p_n$.

Everool 有一个长度为 $2n$ 的二进制字符串 $s$。注意，二进制字符串是指仅由字符 $0$ 和 $1$ 组成的字符串。他希望将 $s$ 划分为两个互不相交且相等的子序列。他需要你帮助完成这一任务。

你被允许恰好执行一次如下操作：

• 你可以任选 $s$ 的一个子序列（可以为空），并将其向右循环移动一位。

换言之，你可以选择一组下标 $b_1, b_2, \ldots, b_m$，满足 $1 \le b_1 \lt b_2 \lt \ldots \lt 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$ 到 $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$。

如果存在某种操作（即选定子序列 $b$）及对应划分，使得 $s$ 可被划分为两个互不相交的子序列 $s^p$ 和 $s^q$，且满足 $s^p = s^q$，则请输出子序列 $b$ 的元素以及子序列 $s^p$ 的下标，即输出 $p_1, p_2, \ldots, p_n$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$), where $2n$ is the length of the binary string.

The second line of each test case contains the binary string $s$ of length $2n$.

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

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），其中 $2n$ 是二进制字符串的长度。

每个测试用例的第二行包含长度为 $2n$ 的二进制字符串 $s$。

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

For each test case, follow the following output format.

If there is no solution, print $-1$.

Otherwise,

• In the first line, print an integer $m$ ($0 \leq m \leq 2n$), followed by $m$ distinct indices $b_1$, $b_2$, ..., $b_m$(in increasing order).
• In the second line, print $n$ distinct indices $p_1$, $p_2$, ..., $p_n$ (in increasing order).

If there are multiple solutions, print any.

对于每个测试用例，请按照以下输出格式输出。

若无解，则输出 $-1$。

否则，

• 在第一行中，先输出一个整数 $m$（$0 \leq m \leq 2n$），随后输出 $m$ 个互不相同的下标 $b_1$, $b_2$, ..., $b_m$（按升序排列）；
• 在第二行中，输出 $n$ 个互不相同的下标 $p_1$, $p_2$, ..., $p_n$（按升序排列）。

若存在多个解，输出任意一个即可。

In the first test case, $b$ is empty. So string $s$ is not changed. Now $s^p = s_1 s_2 = \mathtt{10}$, and $s^q = s_3s_4 = \mathtt{10}$.

In the second test case, $b=[3,5]$. Initially $s_3=\mathtt{0}$, and $s_5=\mathtt{1}$. On performing the operation, we simultaneously set $s_3=\mathtt{1}$, and $s_5=\mathtt{0}$.

So $s$ is updated to 101000 on performing the operation.

Now if we take characters at indices $[1,2,5]$ in $s^p$, we get $s_1=\mathtt{100}$. Also characters at indices $[3,4,6]$ are in $s^q$. Thus $s^q=100$. We are done as $s^p=s^q$.

In fourth test case, it can be proved that it is not possible to partition the string after performing any operation.

在第一个测试用例中，$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}$；而 $s^q$ 包含下标为 $[3,4,6]$ 的字符，故 $s^q=100$。由于 $s^p=s^q$，任务完成。

在第四个测试用例中，可以证明：无论执行何种操作，均无法对字符串进行划分。