BZPRO
#5203. [NEERC2017 Northern]Grand Test
内存限制：512 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
简单路径是指没有重复经过同一个点的路径。
给定一个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，否则第一行输出两个正整数S和T。
接下来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
数据范围与提示
BZPRO