SP1965 SETCOV - Set Cover

在这个集合覆盖问题中，给定一个集合 $C = \{S_1, \ldots, S_m\}$，它是宇宙 $[n] = \{0, \ldots, n-1\}$ 的若干子集组成的。其中需要找出一个最小的子集合，使其仍然能够覆盖整个 $[n]$（注意可能存在某些 $i \neq j$ 使得 $S_i$ 和 $S_j$ 包含完全相同的元素）。一个长度为 $r$ 的路径指的是一个包含 $r+1$ 个顶点 $v_0, \ldots, v_r$ 的图，图中仅存在 $v_i$ 与 $v_{i+1}$ 的无向边连接（$i = 0, \ldots, r-1$）。如果存在一个映射能够从集合覆盖实例 $I$ 到长度为 $m$ 的路径，从而使 $S_i$ 被映射到路径上的边，而且对每个 $i \in [n]$，都有一个对应的顶点对 $s_i, t_i$，以至于 $s_i$ 和 $t_i$ 之间的边恰好对应于包含元素 $i$ 的集合 $C$，那么我们称实例 $I$ 是**路径可实现的**。此外，如果 $i \neq j$，那么 $S_i$ 和 $S_j$ 必须被映射到路径上的不同边。给定一个确保路径可实现的集合覆盖实例，请输出能够覆盖 $[n]$ 的最小子集的大小。

输入的第一行为二维数组 "N M"，其中 $N$ 是宇宙的大小，$M$ 是集合 $C$ 中的子集数量。接下来的 $M$ 组行描述每个子集。每组的第一行为 $|S_i|$，表示第 $i$ 个子集的大小。如果 $|S_i| = 0$，该组输入结束。否则，下一行是一个用空格分隔的整数列表，表示第 $i$ 个子集中的元素。

如果无法用 $C$ 的某个子集覆盖 $[n]$，请输出 `-1`，并换行。否则，输出分两行：第一行是最小集合覆盖的大小；第二行是这个最优解中集合的0开始的索引，空格分隔。

- $1 \le N, M \le 300$ **本翻译由 AI 自动生成**