Description

有 $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$ 个团体应该分别管理哪些栖息地，若有多种分配方式满足条件，输出任意一种。

Input Format

$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$ 条道路连接的栖息地编号。不会有两条不同的道路连接同一对栖息地。

Output Format

输出 $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
5 6
1 2
2 3
3 4
4 5
5 3
4 2

3 3 4 5
1 1
1 2

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

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

Hint

测试数据限制

• $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$。

评分说明

本题共有四组子任务，条件限制如下所示。 每一组可有一或多组测试数据，该组所有测试数据皆需答对才会获得该组分数。