铺设线路

题目描述

某公司承包了一项通信工程，公司得知这片区域内已经存在n座信号塔，编号从1~n，但由于各方面原因，有的信号塔间可以铺设线路，有的信号塔间不可以铺设线路。 工程要求从起点至终点实现通信，起点在s信号塔，终点在e信号塔。为节约成本请你计算最少需要几段通信线缆达成目标。

输入格式

第一行两个整数n和m，n表示信号塔数量，m表示有多少对信号塔之间可铺设线路。（n

输出格式

先输出一个整数，表示达成目标最少线缆的数量，再换行输出路线上经过的结点；无法达成输出-1。

11 17
1 7
8 1
2 8
2 3
3 9
7 11
7 9
8 11
4 9
7 5
9 5
9 10
10 4
11 10
6 10
6 11
8 9
2 5

3
2 3 9 5

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

2
1 3 4

提示

注意：优先铺设编号小的信号塔。

来源

童程童美