<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

260. Puzzle
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Vasya likes to play quests very much. He likes to click here and there and he enjoys jokes which quests are full of. But there are also a lot of different puzzles in quests and Vasya has very hard time solving these puzzles. So once he encountered a puzzle he is unable to solve in spite of all efforts made. But fortunately Vasya is a great programmer and he was able to write a program that helped him to solve the puzzle and complete the quest.
The Vasya's puzzle is a matrix with each of its cells having either black or white color. The click on the cell changes its color and the color of neighboring cells to the opposite one. The goal is to make all the cells to be colored in the same color.
Your task will be a little bit more complicated. Suppose there are N cells numbered from 1 to N. Each cell has a predefined set of cells associated with it. When person clicks on a cell the color of the cells associated with it changes. You will be given a description of all cells groups and initial cells coloring. You should output the sequence of cells which should be clicked to obtain a single color for all the cells. If there are a number of different solutions, you can choose any one.

Input
The first line contains a single integer number N (1 <= N <= 200). The i+1-th line (1 <= i <= N) contains the description of the set of cells associated with i-th cell. Each description starts with the integer number k - number of cells in the set, k distinct integer numbers (numbers of cells) follow. The last line contains N zeroes and ones - initial cells coloring.

Output
If it is impossible to make all cells to be colored the same color, you should output a single number -1. Otherwise you should output integer number L - the number of clicks required to solve the puzzle and then L numbers - cells which are to be clicked.

Sample test(s)

Input
9
3 1 2 4
4 1 2 3 5
3 2 3 6
4 1 4 5 7
5 2 4 5 6 8
4 3 5 6 9
3 4 7 8
4 5 7 8 9
3 6 8 9
1 0 1 0 1 0 1 0 1

Output
9
1 2 3 4 5 6 7 8 9
Author:	Igor A. Kulkin
Resource:	Saratov SU Contest: Golden Fall 2004
Date:	October 2, 2004

<|response|>
## 1) Abridged problem statement (concise)

There are \(N \le 200\) cells, each initially colored 0/1.  
Clicking cell \(i\) toggles (flips 0↔1) the colors of all cells in a given set \(S_i\).

Find any sequence of clicks that makes **all cells end up the same color** (all 0 or all 1).  
If impossible, output `-1`. Otherwise output the number of clicks and the clicked indices.

(Clicking the same cell twice cancels out, so only parity matters.)

---

## 2) Key observations

1. **Everything is XOR / linear over GF(2).**  
   Toggling is XOR with 1, and combining multiple clicks is XOR of their effects.

2. **Each cell is clicked at most once (mod 2).**  
   Let \(x_i \in \{0,1\}\) indicate whether we click cell \(i\) (odd times).

3. **This becomes a linear system.**  
   Final color of cell \(c\) is:
   \[
   a_c \oplus \bigoplus_{i: c \in S_i} x_i
   \]
   We want final color to be a constant target \(t \in \{0,1\}\) for all \(c\). So:
   \[
   \bigoplus_{i: c \in S_i} x_i = a_c \oplus t
   \]
   That is \(N\) linear equations in \(N\) variables over GF(2).

4. **Try both targets.**  
   Solve once for \(t=0\) (all white) and once for \(t=1\) (all black). If either system is solvable, output a solution.

5. **Use bitsets/bitmasks for speed.**  
   \(N \le 200\), and time limit is tight, so do Gaussian elimination mod 2 with bit operations.

---

## 3) Full solution approach

### Step A — Build the matrix \(M\)
Define an \(N \times N\) matrix over GF(2):
- \(M_{c,i} = 1\) iff clicking \(i\) toggles cell \(c\), i.e. \(c \in S_i\).

Then for a chosen target \(t\), define RHS vector:
\[
b_c = a_c \oplus t
\]
We need to solve:
\[
M x = b \quad (\text{over GF(2)})
\]

### Step B — Gaussian elimination over GF(2)
Represent each equation row as a bitset of length \(N+1\):
- Bits \([0..N-1]\): coefficients of variables \(x_0..x_{N-1}\)
- Bit \([N]\): RHS

Perform Gauss-Jordan elimination:
- For each column, find a pivot row with a 1 in that column.
- Swap into position.
- XOR it into all other rows that also have a 1 in that column (this is “subtracting” in GF(2)).

Detect inconsistency:
- If a row has all-zero coefficients but RHS = 1, system is impossible.

### Step C — Extract any solution
After Gauss-Jordan:
- Mark pivot columns.
- Set all free variables to 0.
- Each pivot variable equals the RHS of its pivot row (because other pivot columns were eliminated and free vars are 0).

Collect indices where \(x_i=1\); those are the cells to click.

### Step D — Try both targets
Attempt \(t=0\) and \(t=1\). Output the first solvable solution; otherwise `-1`.

Complexity:
- With bitsets: about \(O(N^3 / w)\) where \(w\) is machine word size, fast enough for \(N=200\).

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Solve linear system over GF(2) with Gauss-Jordan elimination using bitset.

  rows: each row is a bitset of length (MAXN+1).
        bits [0..n-1] are coefficients, bit [n] is RHS.
*/
template <size_t MAXN>
struct GaussXor {
    int n;                              // number of variables
    vector<bitset<MAXN + 1>> rows;      // augmented matrix rows
    vector<int> where;                  // where[col] = pivot row index or -1
    bool solvable = false;

    GaussXor(int n_) : n(n_) {}

    // Add equation: sum_i coeff[i]*x_i = rhs  (mod 2)
    void add_equation(const vector<int>& coeff, int rhs) {
        bitset<MAXN + 1> r;
        for (int i = 0; i < n; i++) {
            if (coeff[i] & 1) r[i] = 1;
        }
        r[n] = rhs & 1;                 // RHS stored at position n
        rows.push_back(r);
    }

    // Gauss-Jordan elimination (eliminate pivot column from all other rows)
    void eliminate() {
        int m = (int)rows.size();
        where.assign(n, -1);

        int r = 0; // current pivot row
        for (int c = 0; c < n && r < m; c++) {
            // Find a pivot row >= r with a 1 in column c
            int sel = -1;
            for (int i = r; i < m; i++) {
                if (rows[i][c]) { sel = i; break; }
            }
            if (sel == -1) continue;    // free variable column

            swap(rows[sel], rows[r]);
            where[c] = r;

            // Eliminate column c from all other rows
            for (int i = 0; i < m; i++) {
                if (i != r && rows[i][c]) {
                    rows[i] ^= rows[r]; // XOR = subtraction in GF(2)
                }
            }
            r++;
        }

        // Check for inconsistency: 0 = 1
        solvable = true;
        for (int i = 0; i < m; i++) {
            bool anyCoeff = false;
            for (int c = 0; c < n; c++) {
                if (rows[i][c]) { anyCoeff = true; break; }
            }
            if (!anyCoeff && rows[i][n]) { // 0*x = 1 impossible
                solvable = false;
                break;
            }
        }
    }

    // Construct one solution by setting free variables = 0.
    // In Gauss-Jordan form, pivot variable equals RHS of its pivot row.
    vector<int> any_solution() const {
        vector<int> x(n, 0);
        for (int v = 0; v < n; v++) {
            if (where[v] != -1) {
                x[v] = rows[where[v]][n];
            }
        }
        return x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<vector<int>> groups(N);

    // Read sets S_i (1-based in input, convert to 0-based)
    for (int i = 0; i < N; i++) {
        int k; cin >> k;
        groups[i].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> groups[i][j];
            groups[i][j]--;
        }
    }

    vector<int> init(N);
    for (int i = 0; i < N; i++) cin >> init[i];

    // Precompute coefficient matrix in a convenient form:
    // For each cell c (equation), coeff[c][i] = 1 iff c in S_i.
    vector<vector<int>> coeff(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int c : groups[i]) {
            coeff[c][i] = 1;
        }
    }

    // Try target color t = 0 then t = 1 (either order is fine)
    for (int t : {0, 1}) {
        GaussXor<200> gauss(N);

        for (int c = 0; c < N; c++) {
            int rhs = init[c] ^ t;
            gauss.add_equation(coeff[c], rhs);
        }

        gauss.eliminate();
        if (!gauss.solvable) continue;

        vector<int> x = gauss.any_solution();
        vector<int> clicks;
        for (int i = 0; i < N; i++) {
            if (x[i]) clicks.push_back(i + 1); // back to 1-based
        }

        cout << clicks.size() << "\n";
        for (int i = 0; i < (int)clicks.size(); i++) {
            cout << clicks[i] << (i + 1 == (int)clicks.size() ? '\n' : ' ');
        }
        if (clicks.empty()) cout << "\n"; // harmless extra newline
        return 0;
    }

    cout << -1 << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

This version uses Python integers as bitmasks (fast for up to 201 bits).

```python
import sys

def gauss_xor(rows, n):
    """
    Gauss-Jordan elimination over GF(2).

    rows: list of int bitmasks, each contains (n coefficient bits) + (1 RHS bit at position n)
    n: number of variables

    Returns: (solvable, where, rows)
      where[col] = pivot row index for that variable, or -1 if free.
      rows is transformed into reduced form.
    """
    where = [-1] * n
    r = 0
    m = len(rows)
    rhs_bit = 1 << n

    for c in range(n):
        if r >= m:
            break
        mask = 1 << c

        # Find pivot row with bit c = 1
        pivot = -1
        for i in range(r, m):
            if rows[i] & mask:
                pivot = i
                break
        if pivot == -1:
            continue  # free variable

        # Move pivot row to position r
        rows[r], rows[pivot] = rows[pivot], rows[r]
        where[c] = r

        # Eliminate bit c from all other rows
        for i in range(m):
            if i != r and (rows[i] & mask):
                rows[i] ^= rows[r]

        r += 1

    # Check inconsistency: all coeffs 0 but RHS 1
    coeff_mask = rhs_bit - 1
    for i in range(m):
        if (rows[i] & coeff_mask) == 0 and (rows[i] & rhs_bit):
            return False, where, rows

    return True, where, rows

def any_solution(where, rows, n):
    """
    With Gauss-Jordan and free vars = 0,
    pivot variable equals RHS bit of its pivot row.
    """
    x = [0] * n
    for v in range(n):
        pr = where[v]
        if pr != -1:
            x[v] = (rows[pr] >> n) & 1
    return x

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))

    groups = []
    for _ in range(n):
        k = int(next(it))
        cur = []
        for _ in range(k):
            cur.append(int(next(it)) - 1)  # to 0-based
        groups.append(cur)

    init = [int(next(it)) for _ in range(n)]

    # Build for each cell c: a bitmask of variables i that affect c (i.e., c in S_i)
    affects = [0] * n
    for i in range(n):
        for c in groups[i]:
            affects[c] |= (1 << i)

    # Try both targets: all 0 or all 1
    for t in (0, 1):
        rows = []
        for c in range(n):
            rhs = init[c] ^ t
            row = affects[c] | (rhs << n)  # augmented row
            rows.append(row)

        solvable, where, red = gauss_xor(rows, n)
        if not solvable:
            continue

        x = any_solution(where, red, n)
        clicks = [str(i + 1) for i, v in enumerate(x) if v == 1]

        sys.stdout.write(str(len(clicks)) + "\n")
        if clicks:
            sys.stdout.write(" ".join(clicks) + "\n")
        else:
            sys.stdout.write("\n")
        return

    sys.stdout.write("-1\n")

if __name__ == "__main__":
    main()
```

