#P5203. 简单路径
简单路径
三条边不相交的路径
简单路径是指没有重复经过同一个点的路径。 给定一个n个点,m条边的简单无向图,问是否能找到两个不同的点S和T,满足S和T之间存在至少三条不同的简单路径。 三条路径中的边两两不重复;每条路径自身也不能重复经过顶点。
输入输出格式
输入格式
从标准输入读入。第一行一个正整数 Case(1<=Case<=100000),表示测试数据的组数。
每组数据第一行包含两个正整数n,m(1<=n,m<=100000),分别表示点数和边数。
接下来m行,每行两个正整数u_i,v_i(1<=u_i<v_i<=n),表示一条无向边。
输入数据保证不存在重边和自环,且sum n,sum m<=100000。
输出格式
对于每组数据,向标准输出写出答案。若无解,输出 -1;否则第一行输出两个不同的点 。
接下来3行描述3条S到T的路径,每行先输出一个正整数t,表示路径上的点数,然后依次从S输出到T路径上的每个点。
若有多组解,输出任意一组。
样例
样例输入
2
6 6
3 6
3 4
1 4
1 2
1 3
2 3
3 1
1 2
样例输出
1 3
3 1 2 3
2 1 3
3 1 4 3
-1