A92170.集合覆盖

题目描述

有 $M$ 个集合 $S_1,S_2,\dots,S_M$，每个集合中的元素都是 $1$ 到 $N$ 之间的整数。
其中第 $i$ 个集合 $S_i$ 一共有 $C_i$ 个元素，分别为 $a_{i,1},a_{i,2},\dots,a_{i,C_i}$。

现在从这 $M$ 个集合中任选至少一个集合进行选择，一共有 $(2^M-1)$ 种选法。
请你统计：有多少种选法能满足下面的要求？

• 对任意整数 $x$（$1\le x\le N$），至少存在一个被选中的集合包含 $x$。换句话说，被选集合的并集需要覆盖 ${1,2,\dots,N}$。

限制因素

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

输出

打印满足问题陈述中条件的集合的选择方式数。

样例一解释

输入中给出的集合为 $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$ 。