#L3354. Political Development

Political Development

题目描述
题目译自 BalticOI 2017 Day1「Political Development」

某党派有 nn 名成员。该党意图谋求新政,计划为此设立委员会。各委员之意见无一相合,且委员会无法再扩大之时,乃良政之始也。
政党为任意两个政治家都安排了一个话题进行讨论,话题是随机选择的,以显示出哪组政治家的意见相合、哪组不合。在政党的《功德册》上会记录每一组意见不统一的政治家。
要想找到一个大的委员会可不简单——经过详细的分析可知,如果在该党派中任选一些党员(人数不限)组成小组,组里至少有一名“墙头草”。小组中与“墙头草”意见不一致的成员严格小于 kk 人。显然,委员会不能有多于 kk 个成员。但是能够选出一个这个大小的委员会吗?

现在要求你根据这本《功德册》,找出尽可能大的委员会,要求各委员的意见统统不一致。

一句话题意
给出一张无向图,满足对于任意导出子图,存在一个节点的度数小于 kk,求原图的最大团。


输入格式
第一行包含两个整数 nnkknn 表示政党成员的人数,kk 如上所述。
每个成员用一个 00n1n-1 之间的整数 ii 表示。
接下来的 nn 行,每行描述一个成员 ii,从 i=0i=0 开始。描述成员 ii 的行以一个整数 did_i 开始,接下来是 did_i 个整数,表示与第 ii 个成员意见不同的成员编号。


输出格式
输出仅一行一个整数,表示最大的委员会成员数。


样例 1
输入

5 3
2 1 2
3 0 2 3
3 0 1 4
2 1 4
2 2 3

输出

3

样例 2
输入

5 3
3 1 2 4
1 0
1 0
0
1 0

输出

2

数据范围与提示
对于 100%100\% 的数据,0di<n5×1040 \le d_i < n \le 5 \times 10^41k101 \le k \le 10

详细子任务与附加限制如下:

  • Subtask 1(4 pts):k2k \le 2n5×103n \le 5 \times 10^3
  • Subtask 2(12 pts):k3k \le 3n5×103n \le 5 \times 10^3
  • Subtask 3(23 pts):di10d_i \le 10
  • Subtask 4(38 pts):n5×103n \le 5 \times 10^3
  • Subtask 5(23 pts):k5k \le 5