You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一个神秘的魔法阵中，有 $N$ 个魔法石，每个魔法石可以处于“激活”或“未激活”两种状态。同时，魔法阵中有 $M$ 个魔法节点，每个魔法节点与若干个魔法石相关联。

第 $i$ 个魔法节点与 $k_i$ 个魔法石相关联，分别为魔法石 $s_{i1}, s_{i2}$, ..., $s_{ik_i}$。当这些魔法石中“激活”状态的数量与 $p_i$ 模 2 同余时，该魔法节点会被激活。

现在需要计算有多少种魔法石的“激活”与“未激活”状态组合可以使所有魔法节点都被激活。

输入

第一行包含两个整数 $N$ 和 $M$ ，分别表示魔法石的数量和魔法节点的数量。

接下来的 $M$ 行，每行描述一个魔法节点：

• 第 $i$ 行的第一个整数 $k_i$ 表示与第 $i$ 个魔法节点相关联的魔法石数量，接下来的 $k_i$ 个整数分别表示这些魔法石的编号。

最后一行包含 $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

提示

• $1 \leq N, M \leq 10$
• $1 \leq k_i \leq N$
• $1 \leq s_{ij} \leq N$
• $s_{ia} \neq s_{ib}$ 即每个魔法节点关联的魔法石编号互不相同
• $p_i 是 0 或 1$