题目描述

在一个黑板上，有 $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