242013 - T4-最小覆盖集合

题目描述

某编程团队需要完成 m 种不同的技能任务,技能编号为 1 到 m。

现在有 n 名学生,每名学生掌握其中若干种技能。

第 i 名学生掌握 k_i 种技能。

你需要从这 n 名学生中选出尽可能少的人,使得被选中的学生掌握的技能能够覆盖全部 m 种技能。

每名学生可以选择,也可以不选择。

如果存在多种方案,只需要输出最少选择人数。

如果无论如何选择,都无法覆盖全部技能,则输出 -1。

输入

第一行输入两个正整数 n,m,分别表示学生数量和技能数量。

接下来 n 行,每行首先输入一个整数 k_i,表示第 i 名学生掌握的技能数量。

随后输入 k_i 个整数,表示该学生掌握的技能编号。

输出

输出一个整数,表示覆盖全部技能需要选择的最少学生人数。

如果不存在合法方案,输出 -1。

样例

输入

4 4
2 1 2
2 2 3
1 4
3 1 3 4

输出

2
说明

样例解释

选择第 1 名和第 4 名学生:

  • 第 1 名学生掌握技能 1,2。
  • 第 4 名学生掌握技能 1,3,4。

两名学生共同覆盖了技能 1,2,3,4。

因此最少需要选择 2 名学生。

数据范围

  • 1\le n\le 20
  • 1\le m\le 20
  • 1\le k_i\le m
  • 技能编号满足 1\le s\le m
  • 同一名学生掌握的技能编号互不相同
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 4 枚
难度 基础


上一题 下一题