Description

简单路径是指没有重复经过同一个点的路径。 给定一个n个点，m条边的简单无向图，问是否能找到两个不同的点S和T，满足S和T之间存在至少三条不同的简单路径。 这三条简单路经之间也不能有重复的边。

Format

Input

输入数据的第一行包含一个正整数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。

Output

对于每组数据，若无解，输出-1，否则第一行输出两个正整数S和T。

接下来3行描述3条S到T的路径，每行先输出一个正整数t，表示路径上的点数，然后依次从S输出到T路径上的每个点。

若有多组解，输出任意一组。

Samples

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

Source 鸣谢Claris提供翻译及SPJ