AT_abc289_c [ABC289C] Coverage

有 $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$ $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 \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$。 ## 样例解释 2 也有可能不存在满足题目条件的选择方法。 由 ChatGPT 4.1 翻译