Subtask 1

This subtask was meant to reward brute-force solutions.

Time Complexity: ~\mathcal O(N \times 2^N)~

Subtask 2

Observe that the answer is always ~N~. We provide a proof later.

Since the answer is always ~N~, we can reduce this problem to a system of equations in ~\mathbb{Z}_2~. Our solution is a vector ~\mathbb{Z}_2^N~, that is to say, a binary vector. We have ~4~ cases:

• If the degree of a node is even and our colour is ~1~, then the number of ~1~s must be even, that is, the right side of our equation must be ~0~.
• If the degree of a node is even and our colour is ~0~, then the number of ~0~s must be even, so the number of ~1~s must be even, so the right side of our equation must be ~0~.
• If the degree of a node is odd and our colour is ~1~, then the number of ~1~s must be even, so the right side of our equation is ~0~.
• If the degree of a node is odd and our colour is ~0~, then the number of ~1~s must be odd, so the right side of our equation is ~1~.

If we represent the system with a matrix, and start with ~A~ as the adjacency matrix, we can set ~A_{ii} = 1~ and ~\vec{b}_i = 1~ if ~\deg(i)~ is odd, and ~A_{ii} = \vec{b}_i = 0~ otherwise, where ~\vec{b}~ is a vector representing the right side of our equation.

In fact, ~\vec{b} = diag(A)~, and ~A~ is symmetric.

We want to prove that this system is consistent. If the system is inconsistent, there exists a linear combination of rows such that the left side reduces to ~\vec{0}~ and the right side reduces to a non-zero number. Since we are operating in ~\mathbb{Z}_2~, this is simply a subset.

Let ~R_1, R_2, \dots, R_k~ be the rows chosen. Since the left side is zero, we have ~A_{R_1R_1} \oplus A_{R_2R_1} \oplus \dots \oplus A_{R_kR_1} = 0~, and similarly for any other column. Then:

$$\displaystyle A_{R_1R_1} \oplus A_{R_2R_1} \oplus \dots \oplus A_{R_kR_1} \oplus A_{R_1R_2} \oplus A_{R_2R_2} \oplus \dots \oplus A_{R_kR_2} \oplus \dots \oplus A_{R_1R_k} \oplus A_{R_2R_k} \oplus \dots \oplus A_{R_kR_k} = 0$$

But we have ~A_{ab} = A_{ba}~, so:

$$\displaystyle A_{R_1R_1} \oplus A_{R_2R_2} \oplus \dots \oplus A_{R_kR_k} = 0$$

but this is just the XOR of the diagonals, which is just the right side of our equation, and we see that it equals ~0~.

We conclude that this system is consistent.

We can solve this system in ~\mathcal O(N^3)~ with Gauss-Jordan.

Time Complexity: ~\mathcal O(N^3)~

Subtask 3

We can optimize the previous solution with a bitset.

Time Complexity: ~\mathcal O(N^3)~

Note 1: It seems like if you write your functions well and compile with -O3 or above, sometimes C++ will just… optimize it into a bitset for you.

Note 2: This problem is solvable in PyPy, if you use a custom bitset, with your bitset size equal to ~63~.

Note 3: Fast I/O is very helpful on this problem, since there can be ~2 \times 10^6~ lines.