Qingshan Loves Strings 2
Contest: Codeforces Round 906 (Div. 1)
Difficulty rating: 1300
Tags: constructive algorithms, greedy, implementation

Qingshan has a string $$$s$$$ which only contains $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

A string $$$a$$$ of length $$$k$$$ is good if and only if

- $$$a_i \ne a_{k-i+1}$$$ for all $$$i=1,2,\ldots,k$$$.

For Div. 2 contestants, note that this condition is different from the condition in problem B.

For example, $$$\texttt{10}$$$, $$$\texttt{1010}$$$, $$$\texttt{111000}$$$ are good, while $$$\texttt{11}$$$, $$$\texttt{101}$$$, $$$\texttt{001}$$$, $$$\texttt{001100}$$$ are not good.

Qingshan wants to make $$$s$$$ good. To do this, she can do the following operation at most $$$300$$$ times (possibly, zero):

- insert $$$\texttt{01}$$$ to any position of $$$s$$$ (getting a new $$$s$$$).

Please tell Qingshan if it is possible to make $$$s$$$ good. If it is possible, print a sequence of operations that makes $$$s$$$ good.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n\le 100$$$) — the length of string $$$s$$$, respectively.

The second line of each test case contains a string $$$s$$$ with length $$$n$$$.

It is guaranteed that $$$s$$$ only consists of $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

Output format:
For each test case, if it impossible to make $$$s$$$ good, output $$$-1$$$.

Otherwise, output $$$p$$$ ($$$0 \le p \le 300$$$) — the number of operations, in the first line.

Then, output $$$p$$$ integers in the second line. The $$$i$$$-th integer should be an index $$$x_i$$$ ($$$0 \le x_i \le n+2i-2$$$) — the position where you want to insert $$$\texttt{01}$$$ in the current $$$s$$$. If $$$x_i=0$$$, you insert $$$\texttt{01}$$$ at the beginning of $$$s$$$. Otherwise, you insert $$$\texttt{01}$$$ immediately after the $$$x_i$$$-th character of $$$s$$$.

We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most $$$300$$$ operations.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can do zero operations and get $$$s=\texttt{01}$$$, which is good.

Another valid solution is to do one operation: (the inserted $$$\texttt{01}$$$ is underlined)

1. $$$\texttt{0}\underline{\texttt{01}}\texttt{1}$$$

and get $$$s = \texttt{0011}$$$, which is good.

In the second and the third test case, it is impossible to make $$$s$$$ good.

In the fourth test case, you can do two operations:

1. $$$\texttt{001110}\underline{\texttt{01}}$$$
2. $$$\texttt{0011100}\underline{\texttt{01}}\texttt{1}$$$

and get $$$s = \texttt{0011100011}$$$, which is good.

Example input:
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001

Example output:
0

-1
-1
2
6 7
1
10
-1

Editorial:
First, there is no solution when the number of 0's and 1's are different.
Otherwise, the construction follows:
If the $$$s_1 \ne s_n$$$ now, we can ignore $$$s_1$$$ and $$$s_n$$$, and consider $$$s_{2..n-1}$$$ as a new $$$s$$$. If $$$s$$$ is empty, the algorithm ends.
Now $$$s_1=s_n$$$. If they are 1, insert 01 to the front; otherwise, insert 01 to the end. Look at this example:
1. "110010"
2. "1001"
3. "011001"
4. "1100"
5. "10"
6. ""
This operation is actually equivalent to moving the last 1 to the front or moving the first 0 to the end. For example, in step 2 to 4 above, we succeed moving the last 1 to the front. So in the worst case, every character in the string are moved, and we need $$$n$$$ moves.
Actually, we don't need $$$n$$$ moves but $$$n/2$$$ moves. Because for the 0 and 1 deleted in the same operation, at most one of them need to be moved.
Time complexity $$$O(n)$$$.