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 \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 翻译