2844 - 团队组建

题目描述

一所大学正在组建科研团队,团队成员将会从学校的各个学术小组中招募。由于资源有限,学校希望尽量减少招募研究人员的数量。

校内共有 N 名同学(编号 1 \sim N),M 个学术小组(编号 1 \sim M)。同一位同学可能隶属于多个不同的学术小组,也可能没有加入任何学术小组。

每个学术小组由若干同学组成,第 i 个学术小组有 K_i 名同学,每个学术小组都有自己的课题。为了保证课题的完整性,如果某个小组中已经有 K_i-1 名成员被招募,则剩下的那位成员也必须被招募

学校要求编号为 1 的同学必须加入科研团队,因为他们是科研团队的负责人。

请你帮助学校计算科研团队在满足招募上述要求的前提下,最少需要招募多少名研究人员。

输入

第一行包含两个整数 NM,分别表示校内学生的总人数和学术小组的数量。

接下来的 M 行,每行描述一个学术小组。每行以一个整数 K_i 开头,表示第 i 个学术小组的成员数,随后是 K_i 个整数,表示该小组的成员编号。

输出

输出一个整数,表示最少需要招募的研究人员数量。

样例

输入

10 4
2 1 3
2 3 4
6 1 2 3 4 6 7
4 4 3 2 1

输出

4

输入

20 8
2 1 7
2 1 11
2 1 18
2 5 1
2 4 5
6 15 17 10 1 3 11
7 5 19 4 18 11 1 12
10 19 14 20 6 12 1 13 7 2 10

输出

6

输入

20 8
2 3 1
5 13 8 7 16 1
2 1 12
5 4 11 14 15 19
5 6 1 20 18 17
5 20 17 12 16 19
8 7 18 8 10 15 2 13 20
8 20 4 8 15 11 3 5 17

输出

3
说明

样例 1 说明

共有 10 名同学和 4 个学术小组:

  • 第 1 个小组包含 13 号,由于 1 号已经招募,因此需要招募 3 号。
  • 第 2 个小组包含 34 号,由于 3 号被招募,因此需要招募 4 号。
  • 第 3 个小组包含 1, 2, 3, 4, 6, 7 号,其中 1 3 4 号被招募。
  • 第 4 个小组包含 1, 2, 3, 4 号,由于 1 3 4 号被招募,因此需要招募 2 号。

最终最少需要招募研究人员编号为 1, 2, 3, 4 共 4 人。

数据范围

对于 30\% 的测评数据,满足 1 \le N,M \le 201 \le K_i \le 101 \le \sum K_i \le 50

对于 50\% 的测评数据,满足 1 \le N \le 10001 \le M \le 3001 \le K_i \le 10001 \le \sum K_i \le 10000

对于所有的测评数据,满足 1 \leq N \leq 200001 \le M \le 20001 \le K_i \le 200001 \leq \sum K_i \leq 250,000

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题