合并集合

题目描述

黑板上写有 $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$ 的集合。如果可能，求出得到它所需的最少操作次数。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• $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 \lt k \le A_i)$
• 输入中的所有值均为整数。