当前没有测试数据。

F - 合并集合

得分: 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$。

你可以进行如下操作任意多次（可能为 0 次）：

• 选择两个有至少一个公共元素的集合 $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。

---

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

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$。

---

1 2
2
1 2

0

$S_1$ 已经包含了 $1$ 和 $M$，所以需要的最小操作数是 $0$。

---

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

-1

---

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

2