## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Equal Binary Subsequences Codeforces Solution

D. Equal Binary Subsequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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},\dots ,{b}_{m}$, where $1\le {b}_{1}<{b}_{2}<\dots <{b}_{m}\le 2n$. After that you simultaneously set

${s}_{{b}_{1}}:={s}_{{b}_{m}},$
${s}_{{b}_{2}}:={s}_{{b}_{1}},$
$\dots ,$
${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},\dots ,{p}_{n}$ and ${q}_{1},{q}_{2},\dots ,{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}}\dots {s}_{{p}_{n}}$${s}^{q}={s}_{{q}_{1}}{s}_{{q}_{2}}\dots {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},\dots ,{p}_{n}$.

Input

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}$.

Output

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\le m\le 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.

Note

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}_{3}{s}_{4}=\mathtt{10}$.

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

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

Now if we take characters at indices $\left[1,2,5\right]$ in ${s}^{p}$, we get ${s}_{1}=\mathtt{100}$. Also characters at indices $\left[3,4,6\right]$ 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.