#CW68. Merge Set(merge)

Merge Set(merge)

题目描述

全集记为 U={1,2,…,M}U=\{1,2,\dots,M\}。黑板开始时有 NN 个集合 S1,S2,…,SNS_1,S_2,\dots,S_N,每个集合都是 UU 的子集;不同编号的集合即使元素完全相同,也仍然视为两个集合。

一次操作选择当前黑板上的两个不同集合 X,YX,Y,并且它们有公共元素,即 X∩Y≠∅X\cap Y\ne\varnothing。擦去这两个集合,再写入一个新集合 X∪YX\cup Y。并集的定义是:X∪YX\cup Y 包含所有属于 XX 或属于 YY 的元素,重复元素只保留一份。其他集合保持不变,一次操作使集合总数减少 11。

若经过若干次操作后,黑板上存在一个集合 TT 同时包含 11 和 MM,就称得到了目标集合。允许进行 00 次操作;如果某个初始集合本身同时包含 11 和 MM,答案就是 00。求得到目标集合所需的最少操作次数;如果无法得到,输出 −1-1。

输入格式

从 merge.in 文件中读入。

第一行包含整数 N,MN,M。

随后对每个 i=1,2,…,Ni=1,2,\dots,N,先输入整数 AiA_i,再输入 AiA_i 个整数 Si,1,Si,2,…,Si,AiS_{i,1},S_{i,2},\dots,S_{i,A_i},表示集合 SiS_i。同一个集合中的这些整数两两不同,但不同集合之间可以出现相同的整数。

输出格式

从 merge.out 文件中输出。

若可以得到目标集合,输出最少操作次数;否则输出 −1-1。不需要输出具体的合并方案。

样例 1 输入

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

样例 1 输出

2

样例 1 解释

集合 S1={1,2}S_1=\{1,2\}、S2={2,3}S_2=\{2,3\}、S3={3,4,5}S_3=\{3,4,5\} 依次共享元素 22 与 33,合并三次一共需要 22 次操作,得到 {1,2,3,4,5}\{1,2,3,4,5\},其中同时含 11 和 55。

样例 2 输入

2 4
2
1 4
1
2

样例 2 输出

0

样例 2 解释

S1={1,4}S_1=\{1,4\} 本身就同时含 11 和 M=4M=4,因此不需要任何操作。

数据范围

所有输入满足 1≤N≤2×1051\le N\le 2\times 10^5、2≤M≤2×1052\le M\le 2\times 10^5、1≤∑i=1NAi≤5×1051\le\sum_{i=1}^{N}A_i\le 5\times 10^5;每个集合中的元素互不相同,且全部属于 [1,M][1,M]。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 15 1∼51\sim 5 N,M≤30N,M\le 30
2 20 6∼106\sim 10 N,M≤1000N,M\le 1000
3 25 11∼1511\sim 15 N≤1000N\le 1000 且 M≤200000M\le 200000
4 40 16∼2016\sim 20 无额外限制,N,M≤2×105N,M\le 2\times 10^5