#P5203. 简单路径

    ID: 2270 传统题 1000ms 512MiB 尝试: 38 已通过: 10 难度: 7 上传者: 标签>难度分类提高枚举与搜索深度优先搜索图论仙人掌图路径恢复CF2200鸣谢Claris提供翻译及SPJ

简单路径

三条边不相交的路径

简单路径是指没有重复经过同一个点的路径。 给定一个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,TS,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