链接: https://cses.fi/problemset/task/1667

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

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

输入

第一行输入包含两个整数 $n$ 和 $m$：计算机数量和连接数。计算机编号为 $1,2,\dots,n$。Uolevi 的计算机是 $1$，Maija 的计算机是 $n$。

接着有 $m$ 行描述连接。每行包含两个整数 $a$ 和 $b$：这两台计算机之间有连接。

每个连接都连接两台不同的计算机，且任意两台计算机之间至多有一个连接。

输出

如果可以发送消息，先输出 $k$：合法路线上最少的计算机数量。之后输出这样一条路线的示例。你可以输出任意合法解。

如果没有路线，输出 "IMPOSSIBLE"。

数据范围

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

样例输入

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

样例输出

3
1 4 5