题目描述
给定一张 n 个点 m 条边的无向图,令 k=⌈mn−1⌉,你需要判断能否找到两个不同的点 u,v,满足它们之间存在 k 条边不相交路径,如果可以找到这样的 u,v,你需要输出这些路径,如果存在多种构造方案,输出任意一种即可。
额外需要注意的是输入可能存在重边,也就是对于同一个无序对 (u,v),它们之间可能存在多条边,如果它们之间存在 s 条边那么你可以理解为这条边可以经过 s 次。
不过我们保证输入不存在自环。
输入格式
从标准输入读入数据。
本题包含多组输入数据。
输入第一行一个正整数 T(1≤T≤104) 表示数据组数。
对于每组输入数据,第一行输入两个正整数 n,m(2≤n≤105,1≤m≤2×105) 表示点数和边数,接下来 m 行每行两个正整数 u,v(1≤u,v≤n,u≠v) 描述 u,v 间存在的一条边。
保证 ∑n≤105,∑m≤2×105。其中 ∑n,∑m 分别表示同一个测试点内所有输入数据的 n,m 之和。
输出格式
输出到标准输出。
对于每组输入数据,如果不存在这样的 u,v,那么输出一行一个整数 -1
,否则先输出一行两个正整数 u,v 表示你找到的两个点,接下来输出 k=⌈mn−1⌉ 行,每行第一个正整数 t 描述你选出来的路径长度,接下来 t 个正整数 x1,x2,…,xt,表示你选择了 x1→x2→⋯→xt 这条路径,你需要保证 x1=u 且 xt=v。且你需要保证输出的 k 条路径满足边不相交的条件。
样例
输入
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
解释
第一组输入数据,存在 ⌈mn−1⌉=⌈13−1⌉=1 条 1 到 3 的边不相交路径 1→3。
第二组输入数据,存在 ⌈mn−1⌉=⌈74−1⌉=3 条 1 到 4 的边不相交路径 1→2→3→4,1→4,1→4,注意到 1→4 这条边虽然经过了两次,但是在原输入中这条边也输入了两次,所以认为它们还是不同的边。
第三组输入数据,存在 ⌈mn−1⌉=⌈55−1⌉=2 条 3 到 5 的边不相交路径 3→4→5,3→5。