题目描述

有 $n$ 个开关和 $m$ 个灯泡，每个开关都处于 “开” 和 “关” 状态中的一种。开关从 $1$ 到 $n$ 编号，灯泡从 $1$ 到 $m$ 编号。

$i$ 号灯泡连接着 $k_i$ 个开关：开关 $s_{i,1}$，$s_{i,2}$，...，$s_{i,k_i}$。当这些开关中，处于 “开” 状态的开关数量之和模 $2$ 余 $p_i$ 时，这个灯泡就会被点亮。

有多少 “开” 和 “关” 的组合，可以点亮所有灯泡？

输入格式

第一行两个正整数 $n, m$，$1\le n,m \le 10$。

接下来 $m$ 行，每行第一个整数为 $k_i$，接下来 $k_i$ 个整数 $s_{i, j}$，$1 \le k_i \le n$，$1 \le s_{i,j} \le n$，$s_{i,a} \neq s_{i,b} (a \neq b)$。

最后一行 $m$ 个整数 $p_i$，$p_i$ 只能是 $0$ 或 $1$。

输出格式

输出一个数，表示有多少总组合方案可以点亮所有灯泡。

2 2
2 1 2
1 2
0 1

1

• 灯泡 $1$ 当以下开关里开着的总数是偶数时会亮：开关 $1$ 和 $2$。
• 灯泡 $2$ 当以下开关里开着的总数是奇数是会亮：开关 $2$。

开关 $1$ 和 $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