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
Discuss Stats
上一题 下一题