← 返回题目列表

AtCoder · abc289_c

F. 覆盖范围

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 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}.

有 (2^M-1) 从以下选项中选择一组或多组的方法 M 设置。
有多少人满足以下条件?

  • 对于所有整数 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}

输出

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


示例输入 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.
以下三种方式满足问题陈述中的条件:

  • 选择 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