#P10258. [2023年重庆八中省队模拟]蛋神的团建

[2023年重庆八中省队模拟]蛋神的团建

蛋神的团建(pvp)

题目描述

共有 nn 名成员,编号为 0,…,n−10,\ldots,n-1。某些成员之间签订了和平条约,条约是双向的。

保证对于成员的任意非空子集,其中至少有一名成员与该子集内其他成员签订的条约数量不超过 kk。

求一个两两之间均签订了和平条约的成员集合,其人数的最大值。也就是求给定无向图的最大团大小。

输入格式

第一行两个整数 n,kn,k。

接下来 nn 行,依次描述编号 0,…,n−10,\ldots,n-1 的成员。每行先给出整数 did_i,再给出 did_i 个与该成员签订条约的成员编号。成员编号均在 [0,n−1][0,n-1] 内。

输出格式

输出一个整数,表示满足要求的最大人数。

样例 1 输入

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

样例 1 输出

3

样例 2 输入

8 2
1 2
3 7 3 5
2 7 0
1 1
1 7
1 1
1 7
4 6 4 1 2

样例 2 输出

2

样例说明

样例 1 中,集合 {0,1,2}\{0,1,2\} 内任意两名成员之间均签订了条约,不存在更大的合法集合。

数据范围

全部数据满足 0≤di<n≤5×1040\le d_i<n\le5\times10^4,1≤k≤101\le k\le10,并满足题目描述中的任意非空子集条件。

子任务 nn 上限 kk 上限 特殊限制 分值
1 20 10 无 15
2 5000
3 50000 5
4 10 di≤kd_i\le k
5 无 40

附加样例 pvp/pvp3.in/ans 至 pvp/pvp6.in/ans 分别满足子任务 2~5 的限制。