A92170.ABC289C - Coverage

问题陈述

有 $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)$ 种。
其中有多少种方法满足下面的条件？

• 对于 $x$ 这样的所有整数 $1 \leq x \leq N$ ，至少有一个所选集合包含 $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}$

输出

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

样例一解释

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