欢迎加入广东最大网戒中心(广东民间OIer、XCPCer交流群):825777247
题目描述
给定一张 个点 条边的无向图,令 ,你需要判断能否找到两个不同的点 ,满足它们之间存在 条边不相交路径,如果可以找到这样的 ,你需要输出这些路径,如果存在多种构造方案,输出任意一种即可。
额外需要注意的是输入可能存在重边,也就是对于同一个无序对 ,它们之间可能存在多条边,如果它们之间存在 条边那么你可以理解为这条边可以经过 次。
不过我们保证输入不存在自环。
输入格式
从标准输入读入数据。
本题包含多组输入数据。
输入第一行一个正整数 表示数据组数。
对于每组输入数据,第一行输入两个正整数 表示点数和边数,接下来 行每行两个正整数 描述 间存在的一条边。
保证 ,。其中 分别表示同一个测试点内所有输入数据的 之和。
输出格式
输出到标准输出。
对于每组输入数据,如果不存在这样的 ,那么输出一行一个整数 -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
样例1解释
第一组输入数据,存在 条 到 的边不相交路径 。
第二组输入数据,存在 条 到 的边不相交路径 ,注意到 这条边虽然经过了两次,但是在原输入中这条边也输入了两次,所以认为它们还是不同的边。
第三组输入数据,存在 条 到 的边不相交路径 。