一所大学正在组建科研团队,团队成员将会从学校的各个学术小组中招募。由于资源有限,学校希望尽量减少招募研究人员的数量。
校内共有 N 名同学(编号 1 \sim N),M 个学术小组(编号 1 \sim M)。同一位同学可能隶属于多个不同的学术小组,也可能没有加入任何学术小组。
每个学术小组由若干同学组成,第 i 个学术小组有 K_i 名同学,每个学术小组都有自己的课题。为了保证课题的完整性,如果某个小组中已经有 K_i-1 名成员被招募,则剩下的那位成员也必须被招募。
学校要求编号为 1 的同学必须加入科研团队,因为他们是科研团队的负责人。
请你帮助学校计算科研团队在满足招募上述要求的前提下,最少需要招募多少名研究人员。
第一行包含两个整数 N 和 M,分别表示校内学生的总人数和学术小组的数量。
接下来的 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
共有 10 名同学和 4 个学术小组:
最终最少需要招募研究人员编号为 1, 2, 3, 4 共 4 人。
对于 30\% 的测评数据,满足 1 \le N,M \le 20,1 \le K_i \le 10,1 \le \sum K_i \le 50。
对于 50\% 的测评数据,满足 1 \le N \le 1000,1 \le M \le 300,1 \le K_i \le 1000,1 \le \sum K_i \le 10000。
对于所有的测评数据,满足 1 \leq N \leq 20000,1 \le M \le 2000,1 \le K_i \le 20000,1 \leq \sum K_i \leq 250,000。