← 返回题目列表

Codeforces · 1572/B

B. 3 的异或

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

给定一个长度为 $$$n$$$ 的序列 $$$a$$$,由 $$$0$$$ 和 $$$1$$$ 组成。

您可以对此序列执行以下操作:

- 从 $$$1$$$ 到 $$$n-2$$$(含)之间选择一个索引 $$$i$$$。
- 同时将 $$$a_{i}$$$、$$$a_{i+1}$$$、$$$a_{i+2}$$$ 全部更改为 $$$a_{i} \oplus a_{i+1} \oplus a_{i+2}$$$,其中 $$$\oplus$$$ 表示按位异或运算

我们可以证明,如果存在一个任意长度的操作序列,将$$$a$$$的所有元素改变为$$$0$$$s,那么也存在这样一个长度不大于$$$n$$$的序列。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2\cdot10^5$$$) — $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = 0$$$ 或 $$$a_i = 1$$$) — $$$a$$$ 的元素。

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

输出

对于每个测试用例,执行以下操作:

- 如果执行多次上述操作后仍无法使 $$$a$$$ 的所有元素都等于 $$$0$$$,则打印“NO”。
- 否则,在第一行打印“YES”,在第二行打印 $$$k$$$ ($$$0 \le k \le n$$$) — 要对 $$$a$$$ 执行的操作数,并在第三行打印序列 $$$b_1, b_2, \dots, b_k$$$ ($$$1 \le b_i \le n - 2$$$) — 应应用操作的索引。

如果有多个解决方案,您可以打印任何一个。

示例

输入 #1

3
3
0 0 0
5
1 1 1 1 0
4
1 0 0 1

输出 #1

YES
0
YES
2
3 1
NO

注意

在第一个示例中,序列仅包含 $$$0$$$,因此我们不需要更改任何内容。

在第二个示例中,我们可以通过对 $$$a$$$ 的第三个元素执行操作,然后对 $$$a$$$ 的第一个元素执行操作,将 $$$[1, 1, 1, 1, 0]$$$ 转换为 $$$[1, 1, 0, 0, 0]$$$,然后转换为 $$$[0, 0, 0, 0, 0]$$$。

在第三个例子中,无论我们先对$$$a$$$的第一个元素还是第二个元素进行操作,都会得到$$$[1, 1, 1, 1]$$$,它不能转换为$$$[0, 0, 0, 0]$$$。