5329. 消息路由（Message Route）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 ## 输入格式 第一行包含两个整数 `n` 和 `m`：分别表示计算机数量和连接数。计算机编号为 `1, 2, \dots, n`，其中乌列维的计算机是 `1`，迈娅的计算机是 `n`。 接下来 `m` 行描述连接关系，每行包含两个整数 `a` 和 `b`，表示计算机 `a` 和 `b` 之间有一条连接。 保证每条连接连接两台不同的计算机，且任意两台计算机之间最多只有一条连接。 ## 输出格式 若存在可行路径： - 首先输出 k：路径上的最少计算机数量。 - 然后输出一行空格分隔的整数，表示该路径（任意有效方案均可）。 若不存在路径，输出 `IMPOSSIBLE`。 ## 输入输出样例 ### 输入 #1 ``` 5 5 1 2 1 3 1 4 2 3 5 4 ``` ### 输出 #1 ``` 3 1 4 5 ``` ## 说明/提示 ### 数据规模与约定 - 2 \le n \le 10^5 - 1 \le m \le 2\times10^5 - 1 \le a, b \le n