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 < b_2 < \ldots < 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$$$.

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

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.

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.