1282 : 图

Description

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

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

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

Input

本题包含多组输入数据。

输入第一行一个正整数 \(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\) 之和。

Output

对于每组输入数据，如果不存在这样的 \(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\) 条路径满足边不相交的条件。

Sample

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 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

Hint

第一组输入数据，存在 \(\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\)。

Source

Author

THU