/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
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 個存在する。
制約
- 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}
出力
問題文の条件を満たす集合の選び方の数を出力せよ。
入力例 1
3 3 2 1 2 2 1 3 1 2
出力例 1
3
入力で与えられている集合はそれぞれ 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 を選ぶ。
入力例 2
4 2 2 1 2 2 1 3
出力例 2
0
問題文の条件を満たす選び方が存在しない場合もあります。
入力例 3
6 6 3 2 3 6 3 2 4 6 2 3 6 3 1 5 6 3 1 3 6 2 1 4
出力例 3
18
Score : 300 points
Problem Statement
There are M sets, called S_1, S_2, \dots, S_M, consisting of integers between 1 and N.
S_i consists of C_i integers a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}.
There are (2^M-1) ways to choose one or more sets from the M sets.
How many of them satisfy the following condition?
- For all integers x such that 1 \leq x \leq N, there is at least one chosen set containing x.
Constraints
- 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
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
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}
Output
Print the number of ways to choose sets that satisfy the conditions in the Problem Statement.
Sample Input 1
3 3 2 1 2 2 1 3 1 2
Sample Output 1
3
The sets given in the input are S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace.
The following three ways satisfy the conditions in the Problem Statement:
- choosing S_1, S_2;
- choosing S_1, S_2, S_3;
- choosing S_2, S_3.
Sample Input 2
4 2 2 1 2 2 1 3
Sample Output 2
0
There may be no way to choose sets that satisfies the conditions in the Problem Statement.
Sample Input 3
6 6 3 2 3 6 3 2 4 6 2 3 6 3 1 5 6 3 1 3 6 2 1 4
Sample Output 3
18