Xor of 3
Contest: Codeforces Round 743 (Div. 1)
Difficulty rating: 2500
Tags: brute force, constructive algorithms, greedy, two pointers

You are given a sequence $$$a$$$ of length $$$n$$$ consisting of $$$0$$$s and $$$1$$$s.

You can perform the following operation on this sequence:

- Pick an index $$$i$$$ from $$$1$$$ to $$$n-2$$$ (inclusive).
- Change all of $$$a_{i}$$$, $$$a_{i+1}$$$, $$$a_{i+2}$$$ to $$$a_{i} \oplus a_{i+1} \oplus a_{i+2}$$$ simultaneously, where $$$\oplus$$$ denotes the bitwise XOR operation

We can prove that if there exists a sequence of operations of any length that changes all elements of $$$a$$$ to $$$0$$$s, then there is also such a sequence of length not greater than $$$n$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$).

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2\cdot10^5$$$) — the length of $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = 0$$$ or $$$a_i = 1$$$) — elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output format:
For each test case, do the following:

- if there is no way of making all the elements of $$$a$$$ equal to $$$0$$$ after performing the above operation some number of times, print "NO".
- otherwise, in the first line print "YES", in the second line print $$$k$$$ ($$$0 \le k \le n$$$) — the number of operations that you want to perform on $$$a$$$, and in the third line print a sequence $$$b_1, b_2, \dots, b_k$$$ ($$$1 \le b_i \le n - 2$$$) — the indices on which the operation should be applied.

If there are multiple solutions, you may print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the sequence contains only $$$0$$$s so we don't need to change anything.

In the second example, we can transform $$$[1, 1, 1, 1, 0]$$$ to $$$[1, 1, 0, 0, 0]$$$ and then to $$$[0, 0, 0, 0, 0]$$$ by performing the operation on the third element of $$$a$$$ and then on the first element of $$$a$$$.

In the third example, no matter whether we first perform the operation on the first or on the second element of $$$a$$$ we will get $$$[1, 1, 1, 1]$$$, which cannot be transformed to $$$[0, 0, 0, 0]$$$.

Example input:
3
3
0 0 0
5
1 1 1 1 0
4
1 0 0 1

Example output:
YES
0
YES
2
3 1
NO

Editorial:
If the xor of all numbers in the array equals $$$1$$$ it is impossible to make everything equal to $$$0$$$, since the parity of all numbers doesn't change after an operation. From now on we will assume that the xor of all numbers equals $$$0$$$.
Lets consider the case when $$$n$$$ is odd. We can perform operations on positions $$$1, 3, ... n-4, n-2$$$. After this for every even $$$i$$$, $$$a_{i-1} = a_i$$$. Additionally, $$$a_n = a_{n-1} = a_{n-2} = 0$$$. Second one is true since the xor of all numbers equals $$$0$$$. Now we can perform operations on positions $$$n-4, n-6, ... 3, 1$$$. This will make the array equal to $$$0$$$.
In the case of even $$$n$$$ we will find a prefix of odd length and even xor of numbers and call the above solution on it and its respective suffix. If there is no such prefix, the solution doesn't exist. Here is a proof of it. Assume that every prefix of odd length has an odd xor. This means that $$$a_1 = a_n = 1$$$ and for every even $$$i < n$$$, $$$a_i = a_{i+1}$$$. Consider an operation on an even position $$$i$$$ (odd is analogous). We know that $$$a_i = a_{i+1}$$$ so after this operation $$$a_i$$$ and $$$a_{i+1}$$$ will be set to $$$a_{i+2}$$$. This means that after every operation for every even $$$i < n$$$, $$$a_i = a_{i+1}$$$ still holds. Thus we will never be able to make $$$a_1$$$ equal to $$$0$$$ since performing an operation on it won't change it.
Summing up, we perform no more than $$$n$$$ operations and our solution runs in $$$O(n)$$$