#P10258. [2023年重庆八中省队模拟]蛋神的团建
[2023年重庆八中省队模拟]蛋神的团建
蛋神的团建(pvp)
题目描述
共有 名成员,编号为 。某些成员之间签订了和平条约,条约是双向的。
保证对于成员的任意非空子集,其中至少有一名成员与该子集内其他成员签订的条约数量不超过 。
求一个两两之间均签订了和平条约的成员集合,其人数的最大值。也就是求给定无向图的最大团大小。
输入格式
第一行两个整数 。
接下来 行,依次描述编号 的成员。每行先给出整数 ,再给出 个与该成员签订条约的成员编号。成员编号均在 内。
输出格式
输出一个整数,表示满足要求的最大人数。
样例 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 中,集合 内任意两名成员之间均签订了条约,不存在更大的合法集合。
数据范围
全部数据满足 ,,并满足题目描述中的任意非空子集条件。
| 子任务 | 上限 | 上限 | 特殊限制 | 分值 |
|---|---|---|---|---|
| 1 | 20 | 10 | 无 | 15 |
| 2 | 5000 | |||
| 3 | 50000 | 5 | ||
| 4 | 10 | |||
| 5 | 无 | 40 |
附加样例 pvp/pvp3.in/ans 至 pvp/pvp6.in/ans 分别满足子任务 2~5 的限制。