102892: [Atcoder]ABC289 C - Coverage

Problem Statement

There are $M$ sets, called $S_1, S_2, \dots, S_M$, consisting of integers between $1$ and $N$.
$S_i$ consists of $C_i$ integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}$.

There are $(2^M-1)$ ways to choose one or more sets from the $M$ sets.
How many of them satisfy the following condition?

• For all integers $x$ such that $1 \leq x \leq N$, there is at least one chosen set containing $x$.

Constraints

• $1 \leq N \leq 10$
• $1 \leq M \leq 10$
• $1 \leq C_i \leq N$
• $1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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}$

Output

Print the number of ways to choose sets that satisfy the conditions in the Problem Statement.

Sample Input 1

3 3
2
1 2
2
1 3
1
2

Sample Output 1

3

The sets given in the input are $S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace$.
The following three ways satisfy the conditions in the Problem Statement:

• choosing $S_1, S_2$;
• choosing $S_1, S_2, S_3$;
• choosing $S_2, S_3$.

Sample Input 2

4 2
2
1 2
2
1 3

Sample Output 2

0

There may be no way to choose sets that satisfies the conditions in the Problem Statement.

Sample Input 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

Sample Output 3

18

问题描述

存在$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}$组成。

有$(2^M-1)$种从$M$个集合中选择一个或多个集合的方式。
有多少种方式满足以下条件？

• 对于所有1到$N$之间的整数$x$，存在一个被选中的集合包含$x$。

约束条件

• $1 \leq N \leq 10$
• $1 \leq M \leq 10$
• $1 \leq C_i \leq N$
• $1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N$
• 输入中的所有值都是整数。

输入

输入通过标准输入给出，格式如下：

$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

样例输出1

3

输入给出的集合是$S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace$。
以下三种方式满足问题描述中的条件：

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

样例输入2

4 2
2
1 2
2
1 3

样例输出2

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

样例输出3

18