← 返回题目列表

AtCoder · abc302_f

I. 合并集

中文机器翻译题面 查看原题

分数: 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