题目描述

有 $M$ 个集合，每个集合由 $1$ 到 $N$ 之间的若干整数构成，依次记为 $S_1, S_2, \dots, S_M$。
集合 $S_i$ 包含 $C_i$ 个整数，分别为 $a_{i,1}, a_{i,2}, \dots, a_{i,C_i}$。

从这 $M$ 个集合中选择至少一个集合的方法共有 $2^M-1$ 种。
在这些选择方法中，满足以下条件的方法有多少种？

• 对于每个满足 $1 \leq x \leq N$ 的整数 $x$，所选的集合中至少有一个集合包含 $x$。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $C_1$ $a_{1,1}$ $a_{1,2}$ $\dots$ $a_{1,C_1}$ $C_2$ $a_{2,1}$ $a_{2,2}$ $\dots$ $a_{2,C_2}$ $\vdots$ $C_M$ $a_{M,1}$ $a_{M,2}$ $\dots$ $a_{M,C_M}$

输出格式

输出满足题目条件的集合选择方法的数量。

样例 1

输入

3 3
2
1 2
2
1 3
1
2

输出

3

样例 2

输入

4 2
2
1 2
2
1 3

输出

0

样例 3

输入

6 6
3
2 3 6
3
2 4 6
2
3 6
3
1 5 6
3
1 3 6
2
1 4

输出

18

说明/提示

限制条件

• $1 \leq N \leq 10$
• $1 \leq M \leq 10$
• $1 \leq C_i \leq N$
• $1 \leq a\_{i,1} < a\_{i,2} < \dots < a\_{i,C\_i} \leq N$
• 所有输入的值均为整数

样例解释 1

输入给出的集合分别为 $S_1 = \{1, 2\}$，$S_2 = \{1, 3\}$，$S_3 = \{2\}$。满足题目条件的集合选择方法有以下 $3$ 种：

• 选择 $S_1, S_2$。
• 选择 $S_1, S_2, S_3$。
• 选择 $S_2, S_3$。

样例解释 2

也有可能不存在满足题目条件的选择方法。

由 ChatGPT 4.1 翻译