题目描述

啊哈沃德第一次来到啊哈星球，得到了啊哈星球的一张地图，地图描述啊哈星球所有城市之间的道路信息，啊哈星球所有的道路都是双向的，啊哈沃德想去所有的城市游玩。城市的编号从1～N。啊哈沃德目前在1号城市，并且他喜欢先去编号小的城市游玩，所有每当到达一个新城市都希望都尽量能去编号小的没去过的城市，如果当前所在城市没有新的城市可以去就会返回上一个城市。请你帮忙计算出啊哈沃德游玩的顺序，每个城市是第几个被访问到的。

输入输出格式

输入格式

第一行的有两个整数n m ，n个顶点，m条边 接下来m行每行是一条类似“a b”这样的数据表示a号顶点和b号顶点之间可以相互到达。

输出格式

输出有两行 第一行是依次输出游玩顺序（城市编号）。 第二行每个城市是第几个被访问到的（按照1~N输出）。

样例1

7 9
1 3
1 5
3 4
3 2
3 5
5 6
5 7
6 7
2 4

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

样例2

13 18
1 5
1 4
3 2
5 2
6 2
2 12
6 7
3 7
3 8
7 8
10 6
6 11
10 11
12 13
12 9
13 9
4 2
5 6

1 4 2 3 7 6 5 10 11 8 12 9 13
1 3 4 2 7 6 5 10 12 8 9 11 13

限制

1<=n<=1000 1<=m<=300000