CSES1667 消息传递
#CS1667. 消息传递
消息传递
题目背景
翻译自 CSES-1667 题。
题目描述
Syrjälä 的网络中有 n 台计算机和 m 条连接。你的任务是判断 Uolevi 是否可以向 Maija 发送消息，如果可以，找出该消息传递路径上最少需要经过的计算机数量。
输入格式
第一行包含两个整数 n 和 m，分别表示计算机的数量和连接的数量。计算机编号为 1,2,…,n1,2,…,n1,2,…,n，其中 Uolevi 的计算机编号为 1，Maija 的计算机编号为 n。
接下来有 m 行，每行包含两个整数 a 和 b，表示计算机 a 和计算机 b 之间有一条连接。
每条连接始终连接两个不同的计算机，且每两台计算机之间至多有一条连接。
输出格式
如果可以发送消息，首先输出一个整数 k，表示有效路径上最少需要经过的计算机数量。接着输出一个示例路径，路径由计算机编号组成，表示消息从 Uolevi 的计算机传递到 Maija 的计算机的路径。
如果没有路径，输出 IMPOSSIBLE。
样例
5 5
1 2
1 3
1 4
2 3
5 4
3
1 4 5
说明/提示