3441：【2024年5月】7级算法等考第1题 最短路径
文件提交：无需freopen
内存限制：256 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：19
解决：0
题目描述
## Description
给定包含n个点，m条边的无向连通图，顶点编号从1到n，每条边的权值均为1，请计算从1号点到n号点的最短路径是多长，并按照访问顺序输出最短路径上经过的顶点，如果最短路径有多条，则输出字典序最小的那条路径。
## Input Format
第一行包含两个整数n，m，分别表示顶点和边的数量，整数之间以一个空格隔开；
接下来m行，每行包含两个整数x，y，表示顶点x和顶点y之间有一条无向边，整数之间以一个空格隔开。
数据范围
测试点1~10：1≤n,m≤105，1≤x,y≤n。
## Output Format
第一行包含一个整数，表示最短路径的长度；
第二行包含若干个整数，表示按照访问顺序输出的最短路径上经过的顶点，如果最短路径有多条，则输出字典序最小的那条路径，整数之间以一个空格隔开。
```input1
4 4
1 2
2 3
1 3
3 4
```
```output1
2
1 3 4
```
```input2
6 6
1 2
1 3
2 4
3 5
4 6
5 6
```
```output2
3
1 2 4 6
```