C - 开关

得分：300分

问题描述

有$N$个开关，每个开关有“开”和“关”两种状态，还有$M$个电灯。开关编号从$1$到$N$，灯泡编号从$1$到$M$。

第$i$个灯泡与$k_i$个开关相关联，分别为开关$s_{i1}$，$s_{i2}$，...，$s_{ik_i}$。当这些开关中“开”状态的数量与$p_i$模$2$同余时，该灯泡会亮。

有多少种开关的“开”和“关”状态组合可以使所有灯泡都亮起来？

约束条件

• $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$。
• 输入中的所有值均为整数。

输入

从标准输入中输入数据，格式如下：

$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$

输出

输出使所有灯泡亮起来的开关的“开”和“关”状态组合的数量。

2 2
2 1 2
1 2
0 1

1

• 灯泡$1$在以下开关的“开”状态数为偶数时会亮起来：开关$1$和$2$。
• 灯泡$2$在以下开关的“开”状态数为奇数时会亮起来：开关$2$。

总共有四种开关状态组合：(开，开)，(开，关)，(关，开)和(关，关)。其中只有(开，开)可以使所有灯泡都亮起来，所以应该输出$1$。

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

0

• 灯泡$1$在以下开关的“开”状态数为偶数时会亮起来：开关$1$和$2$。
• 灯泡$2$在以下开关的“开”状态数为偶数时会亮起来：开关$1$。
• 灯泡$3$在以下开关的“开”状态数为奇数时会亮起来：开关$2$。

为了让灯泡$2$亮起来，开关$1$必须处于“关”状态，而为了让灯泡$3$亮起来，开关$2$必须处于“开”状态。但是这样灯泡$1$将无法亮起来。因此，没有任何一种开关状态组合可以使所有灯泡都亮起来，所以应该输出$0$。

5 2
3 1 2 5
2 2 3
1 0

8