题目描述

有 $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$ 分别代表数字个数与集合的个数。

接下来 $M$ 行，每行首先输入一个整数 $C_i$，代表第 $i$ 个集合的大小。

• 接下来紧接着继续输入 $C_i$ 个空格隔开的数字分别为 $a_{i,1}$ $a_{i,2}$ $\dots$ $a_{i,C_i}$ 对应当前集合的所有元素。

输出格式

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

3 3
2
1 2
2
1 3
1
2

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 \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$。