\(\mathcal Solution\)
\(s^p = s^q\)，即满足 \(s\) 中可以划分成若干段连续序列，这些序列左半部分和右半部分相等。
【无解】
显然当 \(0/1\) 的个数不是偶数时无解。
其他情况有解。
【证明】
证明中的函数名请见下面【证明中的函数意义】。
我们可以构造一组解：
把所有 \(i \le n\)，\(a_{2i} \neq a_{2i + 1}\) 的 \(2i\) 加入集合 \(S\)。
当 \(i \le n\)，\(a_{2i} \neq a_{2i+1}\) 时。必然为 \(\mathtt{01}\) 或者 \(\mathtt{10}\)。
则下标 \(b_i\) 可以构造为 \(\operatorname{one}(S_1), \operatorname{zero}(S_2), \operatorname{one}(S_3), \cdots\)。
那么我们知道只有 \(\operatorname{size}(S) \bmod 2 = 0\) 时成以上 \(b_i\)。
此题当有解时一定时 \(\operatorname{size}(S) \bmod 2 = 0\)。
证明：
当 \(i \le n\)，\(a_{2i} = a_{2i+1}\) 时，\(0/1\) 都是 \(2\) 的倍数，不需考虑。
当 \(i \le n\)，\(a_{2i} \neq a_{2i+1}\) 时。必然为 \(\mathtt{01}\) 或者 \(\mathtt{10}\)。
当 \(\operatorname{size}(S) \bmod 2 \neq 0\) 时，则 \(i \le n\)，\(a_{2i} \neq a_{2i+1}\) 必然出现奇数次，即 \(0/1\) 都是奇数次。
与 【无解】 情况矛盾。
最后 \(p\) 即为 \(1, 3, 5, \cdots, 2n - 1\)。
时间复杂度为 \(\Theta(n)\)。
【证明中的函数意义】
\(\operatorname{one}(i)\) 表示 \(a_i\) 与 \(a_{i+1}\) 是 \(1\) 的位置。
\(\operatorname{zero}(i)\) 表示 \(a_i\) 与 \(a_{i+1}\) 是 \(0\) 的位置。
\(\operatorname{size}(S)\) 表示集合 \(S\) 的大小。
\(\mathcal Code\)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100010, M = 100010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
void solve()
{
int n;
string str;
cin >> n >> str;
int sum = 0;
for (auto x: str) sum += x == '0';
if (sum & 1) cout << -1 << endl;
else
{
vector<int> res;
for (int i = 0; i < n * 2; i += 2)
if (str[i] != str[i + 1])
{
if (str[i] - '0' == res.size() % 2) res.push_back(i + 1);
else res.push_back(i + 2);
}
cout << res.size() << ' ';
for (auto x: res) cout << x << ' ';
cout << endl;
for (int i = 1; i <= n * 2; i += 2) cout << i << ' ';
cout << endl;
}
}
int main()
{
IOS;
cit, cot;
int T = 1;
cin >> T;
while (T -- ) solve();
return 0;
}