分数: 500 点
问题陈述
黑板上有 N 套 S_1,S_2,\dots,S_N 由之间的整数组成 1 和 M。在这里, S_i = \lbrace S_{i,1},S_{i,2},\dots,S_{i,A_i} \rbrace.
您可以执行以下操作任意次数(可能为零):
- 选择两套 X 和 Y 具有至少一个共同元素。 把它们从黑板上擦掉,然后写下来 黑板上改为 X\cup Y 。
在这里, X\cup Y 表示由至少一个中包含的元素组成的集合 X 和 Y.
确定是否可以获得包含两者的集合 1 和 M。 如果可能,求获得它所需的最少操作次数。
约束
- 1 \le N \le 2 \times 10^5
- 2 \le M \le 2 \times 10^5
- 1 \le \sum_{i=1}^{N} A_i \le 5 \times 10^5
- 1 \le S_{i,j} \le M(1 \le i \le N,1 \le j \le A_i)
- S_{i,j} \neq S_{i,k}(1 \le j < k \le A_i)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
A_1
S_{1,1} S_{1,2} \dots S_{1,A_1}
A_2
S_{2,1} S_{2,2} \dots S_{2,A_2}
\vdots
A_N
S_{N,1} S_{N,2} \dots S_{N,A_N}
输出
如果可以获得一套包含两者的 1 和 M,打印获得它所需的最少操作次数;如果不可能,则打印 -1 代替。
样本输入 1
3 5 2 1 2 2 2 3 3 3 4 5
示例输出 1
2
首先选择并删除 \lbrace 1,2 \rbrace 和 \lbrace 2,3 \rbrace 获取 \lbrace 1,2,3 \rbrace.
然后,选择并删除 \lbrace 1,2,3 \rbrace 和 \lbrace 3,4,5 \rbrace 获取 \lbrace 1,2,3,4,5 \rbrace.
因此,可以获得一组包含两者的集合 1 和 M 有两个操作。 由于仅执行一次操作无法达到目的,因此答案是 2.
示例输入 2
1 2 2 1 2
示例输出 2
0
S_1 已包含两者 1 和 M,因此所需的最少操作次数为 0.
示例输入 3
3 5 2 1 3 2 2 4 3 2 4 5
示例输出 3
-1
示例输入 4
4 8 3 1 3 5 2 1 2 3 2 4 7 4 4 6 7 8
示例输出 4
2