题目描述
全集记为 U={1,2,…,M}。黑板开始时有 N 个集合 S1,S2,…,SN,每个集合都是 U 的子集;不同编号的集合即使元素完全相同,也仍然视为两个集合。
一次操作选择当前黑板上的两个不同集合 X,Y,并且它们有公共元素,即 X∩Y=∅。擦去这两个集合,再写入一个新集合 X∪Y。并集的定义是:X∪Y 包含所有属于 X 或属于 Y 的元素,重复元素只保留一份。其他集合保持不变,一次操作使集合总数减少 1。
若经过若干次操作后,黑板上存在一个集合 T 同时包含 1 和 M,就称得到了目标集合。允许进行 0 次操作;如果某个初始集合本身同时包含 1 和 M,答案就是 0。求得到目标集合所需的最少操作次数;如果无法得到,输出 −1。
输入格式
从 merge.in 文件中读入。
第一行包含整数 N,M。
随后对每个 i=1,2,…,N,先输入整数 Ai,再输入 Ai 个整数 Si,1,Si,2,…,Si,Ai,表示集合 Si。同一个集合中的这些整数两两不同,但不同集合之间可以出现相同的整数。
输出格式
从 merge.out 文件中输出。
若可以得到目标集合,输出最少操作次数;否则输出 −1。不需要输出具体的合并方案。
样例 1 输入
3 5
2
1 2
2
2 3
3
3 4 5
样例 1 输出
2
样例 1 解释
集合 S1={1,2}、S2={2,3}、S3={3,4,5} 依次共享元素 2 与 3,合并三次一共需要 2 次操作,得到 {1,2,3,4,5},其中同时含 1 和 5。
样例 2 输入
2 4
2
1 4
1
2
样例 2 输出
0
样例 2 解释
S1={1,4} 本身就同时含 1 和 M=4,因此不需要任何操作。
数据范围
所有输入满足 1≤N≤2×105、2≤M≤2×105、1≤∑i=1NAi≤5×105;每个集合中的元素互不相同,且全部属于 [1,M]。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 |
分值 |
测试点 |
附加条件 |
| 1 |
15 |
1∼5 |
N,M≤30 |
| 2 |
20 |
6∼10 |
N,M≤1000 |
| 3 |
25 |
11∼15 |
N≤1000 且 M≤200000 |
| 4 |
40 |
16∼20 |
无额外限制,N,M≤2×105 |