AT_abc302_f [ABC302F] Merge Set

题目描述

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

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

1 2
2
1 2

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

-1

输入输出样例 #4

输入 #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 翻译