覆盖

题目描述

有 $M$ 个集合,记为 $S_1, S_2, \dots, S_M$,它们由 $1$ 到 $N$ 之间的整数组成。

$S_i$ 由 $C_i$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,C_i}$ 组成。

从这 $M$ 个集合中选择一个或多个,共有 $2^M - 1$ 种方式。

其中有多少种满足以下条件?

对于所有满足 $1 \le x \le 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}$

输出格式

输出满足题目描述中条件的集合选择方式的个数。

样例

3 3
2
1 2
2
1 3
1
2

3

输入给出的集合为 $S_1 = \{1, 2\}, S_2 = \{1, 3\}, S_3 = \{2\}$。

以下三种方式满足题目描述中的条件:

选择 $S_1, S_2$;

选择 $S_1, S_2, S_3$;

选择 $S_2, S_3$。

4 2
2
1 2
2
1 3

0

可能不存在满足题目描述中条件的集合选择方式。

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 \le N \le 10$
• $1 \le M \le 10$
• $1 \le C_i \le N$
• $1 \le a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \le N$
• 输入中的所有值均为整数。