有 $n$ 只猫活动于某个地区，每只猫各有其栖息地，编号为 $1$ 到 $n$。栖息地之间有 $m$ 条道路连接，道路总数不超过 $2n - 4$。第 $i$ 条道路连接第 $a_i$ 个栖息地和第 $b_i$ 个栖息地，猫可以沿着这些道路在栖息地之间双向移动，且不会有两条不同的道路连接着同一对栖息地。有 $3$ 个动保团体要接管此地区，请你协助将这 $n$ 个栖息地分配给这 $3$ 个团体，满足以下要求：

• 每个栖息地仅由 $1$ 个团体管理，且每个团体需要管理至少 $1$ 个栖息地。每个团体所属的栖息地之间不一定要连通。
• 为了方便管理，每个团体会移除由该团体负责的栖息地之间的道路。换句话说，若有一条道路连接的两个栖息地被分配到同一个团体，该道路会被移除。
• 这些道路移除后，剩余的道路不可以形成“环”，以免猫可能会绕着环奔跑，让工作人员难以捉捕。也就是说，不可以存在一个两两相异的栖息地序列 $v_1, v_2, \dots, 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$，表示测试数据个数。

对于每一组测试数据： 第一行包含两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 条道路连接的栖息地编号。

• $n$ 为猫的栖息地数量。
• $m$ 为道路数量。
• $a_i, b_i$ 为第 $i$ 条道路连接的栖息地编号。不会有两条不同的道路连接着同一对栖息地。

输出格式

输出 $t$ 组测试数据的答案。

对于每一组测试数据： 若存在合法的分配方式，请输出三行，每行代表一个团体。第 $i$ 行的格式为： $k_i \ c_{i,1} \ c_{i,2} \ \dots \ c_{i,k_i}$ 其中 $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

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

输出格式 1

3 3 4 5
1 1
1 2

输入格式 2

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

输出格式 2

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