405041: GYM101745 F Yet Another Binary Matrix

For this problem, we will be working in the field mod 2.

Harry has a n × n binary matrix.

Let R denote some set of rows of this matrix, and C denote some set of columns of this matrix. Let W(P, Q) be a |P| by |Q| matrix, where the element in the i-th row and j-th column is equal to the element in the P[i]-th and Q[j]-th row of the given matrix. Notation S[i] means the i-th by value element of set S.

Harry has a subset of the row indices A, and a subset of column indices B.

He would like you to find a subset of column indices X such that the following conditions hold:

1. X is disjoint from B.
2. The rows of W(A, X + B) are linearly independent (see below for definition).
3. The rows of W(R - A, C - X - B) are linearly independent.

If no solution exists, print -1. Otherwise, print any valid subset X.

A set of rows is called linearly independent if and only if there is no subset of rows that sums to a row with all zeros. Remember we are working mod 2, so for example, the rows [1, 0, 1], [1, 1, 0], [0, 1, 1] are not linearly independent since the sum of all these rows is zero. Informally, if we consider each row as a base-2 integer, there is no subset of them that xor to zero.

The first line will contain three integers n, a and b (0 ≤ a, b ≤ n, 1 ≤ n ≤ 50).

The next line will contain a integers, the row indices A₁, A₂, ..., A_a (1 ≤ A_i ≤ n). These indices will be distinct. If a = 0, this line will be left blank.

The next line will contain b integers, the column indices of B₁, B₂, ..., B_b (1 ≤ B_i ≤ n). These indices will be distinct. If b = 0, this line will be left blank.

The next n lines will contain a binary string of length n, representing the binary matrix.

If no solution exists, print -1.

Otherwise, on the first line, print an integer x, the size of your subset X (0 ≤ x ≤ n). The next line should contain x integers, the column indices of X. These indices must be distinct and disjoint from B.

3 1 0
2

001
010
101

1
2

2 1 0
1

11
10

1
2

2 0 0


11
11

-1

6 4 1
1 4 2 3
2
101010
010101
110000
001100
000001
100000

3
3 4 5