[ABC128C] Switches

### 题目描述 有 $n$ 个开关和 $m$ 个灯泡，每个开关都处于“开”和“关”状态中的一种。开关从 $1$ 到 $n$ 编号，灯泡从 $1$ 到 $m$ 编号。 $i$ 号灯泡连接着 $k_i$ 个开关：开关 $s_{i,1}$，$s_{i,2}$，...，$s_{i,k_i}$。当这些开关中，处于“开”状态的开关数量之和模 2 余 $p_i$ 时，这个灯泡就会被点亮。 有多少“开”和“关”的组合，可以点亮所有灯泡？ ### 输入格式 输入来自以下格式的标准输入： --- $ N $ $ M $ $ k_1 $ $ s_{1,1} $ $ s_{1,2} $ $ ... $ $ s_{1,k_1} $ $ : $ $ k_M $ $ s_{M,1} $ $ s_{M,2} $ $ ... $ $ s_{M,k_M} $ $ p_1 $ $ p_2 $ $ ... $ $ p_M $ --- ### 输出格式 输出一个数，表示有多少总组合方案可以点亮所有灯泡。 ### 说明/提示 #### 数据范围 * $1\le N,M \le 10$ * $1 \le k_i \le N$ * $1 \le s_{i,j} \le N$ * $s_{i,a} \neq s_{i,b} (a \neq b)$ * $p_i$ 只能是 $0$ 或 $1$ * 上述所有值都是整数 #### 样例 1/样例 4 * 灯泡 $1$ 当以下开关里开着的总数是偶数时会亮：开关 $1$ 和 $2$。 * 灯泡 $2$ 当以下开关里开着的总数是奇数是会亮：开关 $2$。 开关 $1$ 和 $2$ 一共组成了四种组合：(开，开)，（开，关），（关，开）和（关，关）。其中只有（开，开）满足要求，所以输出 $1$。 #### 样例 2/样例 5 * 灯泡 $1$ 当以下开关里开着的总数是偶数时会亮：开关 $1$ 和 $2$。 * 灯泡 $2$ 当以下开关里开着的总数是偶数时会亮：开关 $1$。 * 灯泡 $3$ 当以下开关里开着的总数是奇数时会亮：开关 $2$。 为了点亮灯泡 $2$，开关 $1$ 必须是关着的；为了点亮灯泡 $3$，开关 $2$ 必须是开着的。但这样灯泡 $1$ 就不能被点亮了。所以，没有组合能让所有灯泡亮起来，故输出 $0$。

[problemUrl]: https://atcoder.jp/contests/abc128/tasks/abc128_c on と off の状態を持つ $ N $ 個の スイッチと、$ M $ 個の電球があります。スイッチには $ 1 $ から $ N $ の、電球には $ 1 $ から $ M $ の番号がついています。 電球 $ i $ は $ k_i $ 個のスイッチに繋がっており、スイッチ $ s_{i1},\ s_{i2},\ ...,\ s_{ik_i} $ のうち on になっているスイッチの個数を $ 2 $ で割った余りが $ p_i $ に等しい時に点灯します。 全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ k_1 $ $ s_{11} $ $ s_{12} $ $ ... $ $ s_{1k_1} $ $ : $ $ k_M $ $ s_{M1} $ $ s_{M2} $ $ ... $ $ s_{Mk_M} $ $ p_1 $ $ p_2 $ $ ... $ $ p_M $

全ての電球が点灯するようなスイッチの on/off の状態の組み合わせの個数を出力せよ。

2 2
2 1 2
1 2
0 1

1

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

0

5 2
3 1 2 5
2 2 3
1 0

8

### 制約 - $ 1\ \leq\ N,\ M\ \leq\ 10 $ - $ 1\ \leq\ k_i\ \leq\ N $ - $ 1\ \leq\ s_{ij}\ \leq\ N $ - $ s_{ia}\ \neq\ s_{ib}\ (a\ \neq\ b) $ - $ p_i $ は $ 0 $ または $ 1 $ - 入力は全て整数である ### Sample Explanation 1 \- 電球 $ 1 $ は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ $ 1,\ 2 $ - 電球 $ 2 $ は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ $ 2 $ (スイッチ $ 1 $、スイッチ $ 2 $) の状態としては (on,on),(on,off),(off,on),(off,off) が考えられますが、このうち (on,on) のみが条件を満たすので、$ 1 $ を出力してください。 ### Sample Explanation 2 \- 電球 $ 1 $ は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ $ 1,\ 2 $ - 電球 $ 2 $ は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ $ 1 $ - 電球 $ 3 $ は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ $ 2 $ 電球 $ 2 $ を点灯させるためには スイッチ $ 1 $ が off, 電球 $ 3 $ を点灯させるためにはスイッチ $ 2 $ が on である必要がありますが、この時電球 $ 1 $ は点灯しません。 よって、全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは存在しないので、$ 0 $ を出力してください。