AT_abc302_f.[ABC302F] Merge Set

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

黑板上写有 $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$ 。

输入格式

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

$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
```
输入#2
```
1 2
2
1 2
```
输出#2
```
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
```

说明/提示

限制条件

$1 \leq N \leq 2 \times 10^5$
$2 \leq M \leq 2 \times 10^5$
$1 \leq \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)$
输入均为整数。

样例解释 1

首先，选择 $\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$ 。这样经过 $2$ 次操作可以得到同时包含 $1$ 和 $M$ 的集合。由于一次操作无法达成目标，答案为 $2$ 。

样例解释 2

一开始 $S_1$ 就同时包含 $1$ 和 $M$ ，因此最小操作次数为 $0$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页