Message Route

题目描述

Syrjälä 的网络有 n 台计算机和 m 条连接。你的任务是判断 Uolevi 是否可以向 Maija 发送消息，如果可能，找出这样一条路径上计算机的最小数量。

输入格式

第一行输入包含两个整数 n 和 m：计算机的数量和连接的数量。计算机编号为 1,2,\dots,n。Uolevi 的计算机是 1，Maija 的计算机是 n。 接下来有 m 行描述连接。每行包含两个整数 a 和 b：表示这两台计算机之间有一条连接。 每条连接都在两个不同的计算机之间，并且任意两台计算机之间最多有一条连接。

输出格式

如果可以发送消息，首先输出 k：一条有效路径上计算机的最小数量。随后，输出这样一条路径的示例。你可以输出任意一个有效解。 如果不存在路径，输出 "IMPOSSIBLE"。

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

3
1 4 5

提示

$2 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES1667|图论

来源

CSES1667|图论