当前没有测试数据。

C - 范围覆盖

得分：300分

问题描述

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

输出

输出满足问题描述中条件的选择集合的数量。

3 3
2
1 2
2
1 3
1
2

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

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