问题描述

给定 $N$ 个集合 $S_1, S_2, \ldots, S_N$。第 $i$ 个集合 $S_i$ 的大小为 $A_i$，包含介于 $1$ 和 $M$ 之间（含）的整数元素。保证集合中的元素互不相同。

你可以进行以下操作任意次：

• 选择两个至少包含一个公共元素的集合 $S_i$ 和 $S_j$。将这两个集合删除，并添加一个新的集合 $S_i \cup S_j$（即两个集合的并集）。

求使得存在一个集合同时包含整数 $1$ 和整数 $M$ 所需的最少操作次数。如果无法实现，输出 -1。

输入格式

输入从标准输入按以下格式给出： 第一行两个整数$N$和$M$ 接下来2*n行，第一个数代表集合$s_i$的大小$k$,接下来k个数$s_{i,1},s_{i,2}...$ 详情请见样例

输出格式

输出使得存在一个集合同时包含 $1$ 和 $M$ 所需的最少操作次数。如果无法实现，输出 -1。

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

2

样例解释

首先，选取并移除{1,2}和{2,3}，得到{1,2,3}。

接着，选取并移除{1,2,3}和{3,4,5}，得到{1,2,3,4,5}。

因此，通过两次操作可以得到一个同时包含1和M的集合。由于仅进行一次操作无法达成目标，所以答案是2 。

1 2
2
1 2

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 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 2 \times 10^5$
• $1 \leq A_i$
• $\sum_{i=1}^{N} A_i \leq 5 \times 10^5$
• $1 \leq S_{i,j} \leq M$ $(1 \leq i \leq N, 1 \leq j \leq A_i)$
• $S_{i,j} \neq S_{i,k}$ $(1 \leq j < k \leq A_i)$
• 输入中的所有值均为整数。