[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 2𝑛$2n$. Note that a binary string is a string consisting of only characters 0$0$ and 1$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 𝑏1,𝑏2,…,𝑏𝑚$b_1,b_2,\dots ,b_m$, where 1≤𝑏1<𝑏2<…<𝑏𝑚≤2𝑛$1\le b_1<b_2<\dots <b_m\le 2n$. After that you simultaneously set

𝑠𝑏1:=𝑠𝑏𝑚,$$s_{b_1}:=s_{b_m},$$

𝑠𝑏2:=𝑠𝑏1,$$s_{b_2}:=s_{b_1},$$

…,$$\dots ,$$

𝑠𝑏𝑚:=𝑠𝑏𝑚−1.$$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 𝑝1,𝑝2,…,𝑝𝑛$p_1,p_2,\dots ,p_n$ and 𝑞1,𝑞2,…,𝑞𝑛$q_1,q_2,\dots ,q_n$, such that each integer from 1$1$ to 2𝑛$2n$ is encountered in either 𝑝$p$ or 𝑞$q$ exactly once, 𝑠𝑝=𝑠𝑝1𝑠𝑝2…𝑠𝑝𝑛$s^p=s_{p_1}{s}_{p_2}\dots s_{p_n}$, 𝑠𝑞=𝑠𝑞1𝑠𝑞2…𝑠𝑞𝑛$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$-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 𝑝1,𝑝2,…,𝑝𝑛$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≤𝑡≤105$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≤𝑛≤105$1\le n\le {10}^5$), where 2𝑛$2n$ is the length of the binary string.

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

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

Output

For each test case, follow the following output format.

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

Otherwise,

• In the first line, print an integer 𝑚$m$ (0≤𝑚≤2𝑛$0\le m\le 2n$), followed by 𝑚$m$ distinct indices 𝑏1$b_1$, 𝑏2$b_2$, ..., 𝑏𝑚$b_m$(in increasing order).
• In the second line, print 𝑛$n$ distinct indices 𝑝1$p_1$, 𝑝2$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 𝑠𝑝=𝑠1𝑠2=𝟷𝟶$s^p=s_1{s}_2=\mathtt{10}$, and 𝑠𝑞=𝑠3𝑠4=𝟷𝟶$s^q=s_3{s}_4=\mathtt{10}$.

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

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

Now if we take characters at indices [1,2,5]$[1,2,5]$ in 𝑠𝑝$s^p$, we get 𝑠1=𝟷𝟶𝟶$s_1=\mathtt{100}$. Also characters at indices [3,4,6]$[3,4,6]$ are in 𝑠𝑞$s^q$. Thus 𝑠𝑞=100$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.