P11777 [COTS 2013] 集合求解 / BOMBONI

存在若干个集合（集合数量未知，不存在空集），给定 $n$，每个集合中元素 $x$ 满足 $1 \le x \le n$，你现在已知 $M$ 个集合内的元素情况。 定义全集 $U=\{1,2,\dots ,n\}$，这若干个集合间满足两个性质： - 若集合 $A$ 存在，那么 $\complement_UA$ 也存在。 - 对于当前的两个集合 $A,B$，集合 $C=A \cup B$ 也存在。 希望你求出最小的集合数量，把它对 $10^9+9$ 取模的结果。

第一行一个整数 $n$。 第二行一个整数 $M$，表示已知的集合数量。 以下 $M$ 行，一行一个整数 $B$，表示当前集合元素数量，随后是 $B$ 个数字，表示集合元素。

一行一个整数，即最小集合数量对 $10^9+9$ 取模的结果。

【样例解释】 - 对于第一个样例，集合为 $\{1,2\},\{3\},\{1,2,3\}$。 - 对于第二个样例，另外的 $5$ 个集合为 $\{1, 2, 9, 10\},\{1,2,3,4,7,8,9,10\},\{1,2,3,4,5,6,7,8,9,10\},\{3,4,7,8\},\{1,2,5,6,9,10\}$。 【数据范围与约定】 - 对于 $40\%$ 的数据，满足 $n \le 30$，答案不超过 $5000$。 - 对于 $100 \%$ 的数据，满足 $1\le n \le 2\times 10^5,1\le M \le 50$。