#ABC128C. 灯泡开关

灯泡开关

AT_abc128_c [ABC128C] Switches

题目描述

\hspace{15pt}有 nn 个开关和 mm 个灯泡,每个开关都处于「开」和「关」状态中的一种。开关从 11 到 nn 编号,灯泡从 11 到 mm 编号。

\hspace{15pt}第 ii 个灯泡连接着 kik_i 个开关 si,1,si,2,…,si,kis_{i,1},s_{i,2},\dots,s_{i,k_i}。当这些开关中处于「开」状态的开关数量对 22 取模的结果等于 pip_i 时,这个灯泡就会被点亮。

\hspace{15pt}请问有多少种「开」和「关」的组合,可以点亮所有灯泡?

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦10)n,m \left(1 \leqq n,m \leqq 10\right) 代表开关数量和灯泡数量。

\hspace{15pt}此后 mm 行,第 ii 行先输入一个整数 ki(1≦ki≦n)k_i \left(1 \leqq k_i \leqq n\right) 代表第 ii 个灯泡连接的开关数量,随后输入 kik_i 个互不相同的整数 $s_{i,1},s_{i,2},\dots,s_{i,k_i} \left(1 \leqq s_{i,j} \leqq n\right)$ 代表这些开关的编号。

\hspace{15pt}最后一行输入 mm 个整数 p1,p2,…,pm(pi∈{0,1})p_1,p_2,\dots,p_m \left(p_i \in \{0,1\}\right) 代表第 ii 个灯泡被点亮所需的奇偶性。

输出格式

\hspace{15pt}在一行上输出一个整数,代表可以点亮所有灯泡的「开」和「关」组合数量。

测试样例

2 2
2 1 2
1 2
0 1
1

样例 1 解释

\hspace{15pt}灯泡 11 连接开关 11 和 22,当这两个开关中处于「开」状态的开关数量为偶数时点亮(p1=0p_1=0);灯泡 22 连接开关 22,当开关 22 处于「开」状态时点亮(p2=1p_2=1)。

\hspace{15pt}开关 11 和 22 一共有 44 种组合,其中只有(开,开)能同时点亮两个灯泡,所以输出 11。

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

样例 2 解释

\hspace{15pt}灯泡 11 连接开关 11 和 22,要求其中处于「开」状态的开关数量为偶数;灯泡 22 连接开关 11,要求开关 11 处于「开」状态;灯泡 33 连接开关 22,要求开关 22 处于「开」状态。

\hspace{15pt}为了点亮灯泡 22,开关 11 必须是关着的;为了点亮灯泡 33,开关 22 必须是开着的。但这样灯泡 11 对应的「开」状态开关数量为 11,是奇数,灯泡 11 不能被点亮。所以没有组合能让所有灯泡亮起来,输出 00。

5 2
3 1 2 5
2 2 3
1 0
8