P11829 [TOIP2024] 栖息地分配

有 $n$ 只猫活动于某个地区，每只猫各有其栖息地，编号为 $1$ 到 $n$。栖息地之间有 $m$ 条道路连接，道路总数不超过 $2n-4$。第 $i$ 条道路连接第 $a_i$ 个栖息地和第 $b_i$ 个栖息地，猫可以沿着这些道路在栖息地之间**双向**移动，且不会有两条不同的道路连接着同一对栖息地。有 $3$ 个动物保护团体要接管此地区，请你协助将这 $n$ 个栖息地分配给这 $3$ 个团体，满足以下要求： - 每个栖息地仅由 $1$ 个团体管理，且每个团体需要管理至少 $1$ 个栖息地。每个团体所属的栖息地之间不一定要连通。 - 为了方便管理，每个团体会移除由该团体负责的栖息地之间的道路。换句话说，若有一条道路连接的两个栖息地被分配到同一个团体，该道路会被移除。 - 这些道路移除后，剩余的道路不可以形成「环」，以免猫可能会绕着环奔跑，让工作人员难以捕捉。也就是说，不可以存在一个两两相异的栖息地序列 $v_1,v_2,\ldots, v_k$，满足 $k \ge 3$，且对于所有 $1\le i < k$，栖息地 $v_i$ 和栖息地 $v_{i+1}$ 都有一条未被移除的道路连接、同时 $v_k$ 和 $v_1$ 也有一条未被移除的道路连接。 举例，有 $5$ 个栖息地，道路连接如下图所示  我们可以将第 $3$, $4$, $5$ 个栖息地分配给第 $1$ 个团体，第 $1$ 个栖息地分配给第 $2$ 个团体，第 $2$ 个栖息地分配给第 $3$ 个团体。 移除掉道路后，如下图所示  剩余道路不存在环，所以这是一种满足目标的分配方式。 请输出这 $3$ 个团体应该分别管理哪些栖息地，若有多种分配方式满足条件，输出任意一种。

> $t$ > $test_1$ > $test_2$ > $\vdots$ > $test_t$ * $t$ 表示测试数据个数。 * $test_i$ 为第 $i$ 组测试数据。 每一组测试数据的输入格式如下： > $n$ $m$ > $a_1$ $b_1$ > $a_2$ $b_2$ > $\vdots$ > $a_m$ $b_m$ * $n$ 为猫的栖息地数量。 * $m$ 为道路数量。 * $a_i, b_i$ 为第 $i$ 条道路连接的栖息地编号。不会有两条不同的道路连接同一对栖息地。

输出 $t$ 组测试数据之答案： > $answer_1$ > $answer_2$ > $\vdots$ > $answer_t$ * $answer_i$ 为第 $i$ 组测试数据之答案。 每一组测试数据答案的输出格式如下： > $k_1$ $c_{1,1}$ $\cdots$ $c_{1,k_1}$ > $k_2$ $c_{2,1}$ $\cdots$ $c_{2,k_2}$ > $k_3$ $c_{3,1}$ $\cdots$ $c_{3,k_3}$ * $k_i$ 为第 $i$ 个团体分配到的栖息地总数。 * $c_{i,j}$ 为第 $i$ 个团体分配到的第 $j$ 个栖息地。 若该组测试数据不存在所求的分法，请输出 `-1`。

### 测试数据限制 * $1 \le t \le 3\times 10^5$。 * $3 \le n \le 3\times 10^5$。 * $0 \le m \le 2n - 4$。 * $1 \le a_i, b_i \le n$，$a_i \neq b_i$。 * 所有测试数据中，$n$ 的总和不超过 $3\times 10^5$。 ### 评分说明 本题共有四组子任务，条件限制如下所示。 每一组可有一或多组测试数据，该组所有测试数据皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | $3$ | 输入满足 $m = n - 1$，且所有的栖息地连通。 | | 2 | $23$ | 输入保证存在两个以上的栖息地互相无法抵达。 | | 3 | $28$ | 输入满足所有测试数据中，$n$ 的总和不超过 $500$。 | | 4 | $46$ | 无额外限制。 |