← 返回题目列表

Codeforces · 2192/B

B. 翻转二进制字符串

中文机器翻译题面 查看原题

给你一个长度为$$$n$$$的二进制字符串$$$s$$$。您可以对字符串执行以下操作:

  • 选择索引 $$$i$$$,并翻转除索引 $$$i$$$ 之外的所有其他索引中存在的位。换句话说,选择一个整数 $$$i$$$ ($$$1 \le i \le n$$$),并且对于所有 $$$j$$$ 使得 $$$1 \le j \le n$$$ 和 $$$j \ne i$$$,如果 $$$s_j = 0$$$,则设置 $$$s_j:=1$$$,否则设置 $$$s_j:=0$$$。

您可以执行任意次操作,但每个索引可以通过以下方式选择 最多 1 个 操作。

您的任务是使字符串 $$$s$$$ 中存在的所有位都等于 $$$0$$$,或者报告不可能这样做。您不必最小化操作次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含长度为$$$n$$$的二进制字符串$$$s$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果不可能将所有位转换为 $$$0$$$,则输出 $$$-1$$$。否则,按以下格式输出两行:

  • 在第一行中,打印操作数 $$$x$$$ ($$$0 \leq x \leq n$$$)。
  • 在每个测试用例的第二行中,打印 $$$x$$$ 数字 – 您在每个操作中按顺序选择的索引。您应该保证每个索引最多被选择一次。

如果有多种可能的解决方案,您可以输出任何一个。

示例

输入
复制

4
3
101
3
100
4
0000
4
1010

输出
复制

1
2
-1
0
2
1 3

注意

在第一个测试用例中,对索引 $$$2$$$ 执行操作意味着翻转索引 $$$1$$$ 和 $$$3$$$ 处存在的位。因此形成的新字符串将为$$$000$$$。

在第二个测试用例中,可以表明我们无法使用所描述的操作使字符串 $$$a$$$ 等于 $$$000$$$。