Illuminating the Campus

Before the start of ROI, the campus director has decided for each building and each corridor whether it should be illuminated. You are given a set of operations that can toggle (i.e., flip) the state of a subset of lights. Initially, all lights are off. Each operation, when applied, will change the state (from off to on or on to off) of a given subset of lights.

You are given an integer \(N\) representing the total number of lights (each light representing a building or corridor) and an integer \(M\) representing the number of available operations. The director's requirement is given as a binary array \(b[1..N]\) where \(b_i = 1\) means the light \(i\) must be on, and \(b_i = 0\) means it must be off.

For each operation, you are provided an integer \(k\) indicating the number of lights that the operation toggles, followed by \(k\) distinct integers representing the indices of these lights. Note that each operation can be applied at most once, and operations can be performed in any order. Formally, if you denote by \(x_j \in \{0,1\}\) whether you apply the \(j\)-th operation, then for every light \(i\) the following must hold in \(\text{mod }2\):

[ \sum_{j:, i\in S_j} x_j \equiv b_i , (\bmod,2), ]

Your task is to determine if there exists a subset of operations such that, when applied, the resulting state of the lights matches the director's requirements. If such a sequence exists, output any valid sequence (i.e. the indices of operations chosen). If it is impossible, output -1.

Note: Even if you only determine whether the desired light state is achievable (without providing the full sequence), your solution might receive partial credit.

inputFormat

The first line contains two integers \(N\) and \(M\) (1 ≤ N, M ≤ 1000) denoting the number of lights and the number of operations, respectively.

The second line contains \(N\) integers \(b_1, b_2, ..., b_N\) where each \(b_i\) is either 0 or 1, representing the desired state for light \(i\>.

The next \(M\) lines describe the operations. Each operation is given in one line starting with an integer \(k\) (1 ≤ k ≤ N) followed by \(k\) distinct integers indicating the indices of the lights that this operation toggles.

outputFormat

If it is impossible to achieve the desired state, output a single line with -1.

Otherwise, on the first line output an integer \(L\) denoting the number of operations used, and on the second line output \(L\) space-separated integers representing the 1-indexed indices of the operations applied (in any order).

sample

3 3
1 0 1
2 1 2
2 2 3
2 1 3

2
1 2