题目描述

给定一张 $n$ 个点 $m$ 条边的无向图，令 $k=\lceil\frac{m}{n-1}\rceil$，你需要判断能否找到两个不同的点 $u,v$，满足它们之间存在 $k$ 条边不相交路径，如果可以找到这样的 $u,v$，你需要输出这些路径，如果存在多种构造方案，输出任意一种即可。

额外需要注意的是输入可能存在重边，也就是对于同一个无序对 $(u,v)$，它们之间可能存在多条边，如果它们之间存在 $s$ 条边那么你可以理解为这条边可以经过 $s$ 次。

不过我们保证输入不存在自环。

输入格式

本题包含多组输入数据。

输入第一行一个正整数 $T(1\le T\le 10^4)$ 表示数据组数。

对于每组输入数据，第一行输入两个正整数 $n,m(2\le n\le 10^5,1\le m\le 2\times 10^5)$ 表示点数和边数，接下来 $m$ 行每行两个正整数 $u,v(1\le u,v\le n,u\not=v)$ 描述 $u,v$​ 间存在的一条边。

保证 $\sum n\le 10^5$，$\sum m\le 2\times 10^5$。其中 $\sum n,\sum m$ 分别表示同一个测试点内所有输入数据的 $n,m$ 之和。

输出格式

对于每组输入数据，如果不存在这样的 $u,v$，那么输出一行一个整数 -1，否则先输出一行两个正整数 $u,v$ 表示你找到的两个点，接下来输出 $k=\lceil\frac{m}{n-1}\rceil$ 行，每行第一个正整数 $t$ 描述你选出来的路径长度，接下来 $t$ 个正整数 $x_1,x_2,\dots,x_t$，表示你选择了 $x_1\to x_2\to\cdots\to x_t$ 这条路径，你需要保证 $x_1=u$ 且 $x_t=v$。且你需要保证输出的 $k$ 条路径满足边不相交的条件。

输入输出样例 #1

输入 #1

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

输出 #1

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

说明/提示

第一组输入数据，存在 $\lceil\frac{m}{n-1}\rceil=\lceil\frac{1}{3-1}\rceil=1$ 条 $1$ 到 $3$ 的边不相交路径 $1\to 3$。

第二组输入数据，存在 $\lceil\frac{m}{n-1}\rceil=\lceil\frac{7}{4-1}\rceil=3$ 条 $1$ 到 $4$ 的边不相交路径 $1\to 2\to 3\to 4,1\to 4,1\to 4$，注意到 $1\to 4$ 这条边虽然经过了两次，但是在原输入中这条边也输入了两次，所以认为它们还是不同的边。

第三组输入数据，存在 $\lceil\frac{m}{n-1}\rceil=\lceil\frac{5}{5-1}\rceil=2$ 条 $3$ 到 $5$ 的边不相交路径 $3\to 4\to 5,3\to 5$。