题目描述

在广阔的大陆上有 $n$ 个城市（编号为 $1$ \sim $n$ ），城市之间修建了 $m$ 条双向的道路，且任意两个城市之间最多只有 $1$ 条路。

请编程输出，从 $1$ 号城市到 $n$ 号城市的所有可行的路线，为了节约时间，每条路线都不会重复的经过同一个点。

请按字典码从小到大的顺序，输出每一条道路，如果道路数量超过 $1000$ 条，你只需要输出前 $1000$ 条道路。

输入

第 $1$ 行，有 $2$ 个整数 $n$ 和 $m$ 。（ $1≤n≤100$,$1≤m≤(n-1)×n/2$ ）

接下来 $m$ 行，每行有 $2$ 个整数 $x$ 和 $y$ ，表示两个城市之间有一条双向道路。（ $1≤x,y≤n$ ， $x \neq y$ ，两个城市之间至多只有一条双向道路）

输出

输出从 $1$ 号城市到 $n$ 号城市的所有路线，按照字典码从小到大的顺序输出，每行输出 $1$ 条路线，路线数超过 $1000$ 条，只需要输出前 $1000$ 条；本题的测试数据保证从 $1$ 号城市到 $n$ 号城市，至少存在一条可以走到的路径。

样例

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

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