405029 - 哈密尔顿环

有一张地图,它可以看成是一张无向图,试输出图中所有不重复的哈密尔顿环。

Input

输入的第一行有两个整数n和m,表示顶点个数及线段数。 随后m行,每行两个整数表示线段的两个顶点。

Output

每行一串数字,表示一个哈密尔顿环。

Examples

Input

5 7 
1 2
1 5
2 3
2 4
2 5
3 4
4 5

Output

1 2 3 4 5 1
1 2 4 5 1
1 2 5 1
2 3 4 2
2 3 4 5 2
2 4 5 2
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题