题目描述

$1$ 以上 $N$ 以下の整数からなる集合が $M$ 個あり、順に $S_1,\ S_2,\ \dots,\ S_M$ と呼びます。
$S_i$ は $C_i$ 個の整数 $a_{i,\ 1},\ a_{i,\ 2},\ \dots,\ a_{i,\ C_i}$ からなります。

$M$ 個の集合から $1$ 個以上の集合を選ぶ方法は $2^M-1$ 通りあります。
このうち、次の条件を満たす選び方は何通りありますか？

• $1\ \leq\ x\ \leq\ N$ を満たす全ての整数 $x$ に対して、選んだ集合の中に $x$ を含む集合が少なくとも $1$ 個存在する。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

問題文の条件を満たす集合の選び方の数を出力せよ。

题目大意

有 $M$ 个集合，其中选出 $k$ 个，使这 $k$ 个集合的并集包含 $1$ 到 $N$ 中的任何一个数，求有多少种选法。

3 3
2
1 2
2
1 3
1
2

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

提示

制約

• $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 $
• 入力される値は全て整数

Sample Explanation 1

入力で与えられている集合はそれぞれ $ S_1\ =\ \lbrace\ 1,\ 2\ \rbrace,\ S_2\ =\ \lbrace\ 1,\ 3\ \rbrace,\ S_3\ =\ \lbrace\ 2\ \rbrace $ です。 問題文の条件を満たす集合の選び方は次の $3$ 通りです。 - $S_1,\ S_2$ を選ぶ。 - $S_1,\ S_2,\ S_3$ を選ぶ。 - $S_2,\ S_3$ を選ぶ。

Sample Explanation 2

問題文の条件を満たす選び方が存在しない場合もあります。