雪线尽头

题目描述

雪线高原上有 $n$ 个补给站，编号为 $1$ 到 $n$。站点之间通过若干条双向山路连接。

探路员从补给站 $s$ 出发，每次沿一条山路前进到相邻站点。现在他想知道： 在所有离 $s$ 最远的补给站中，编号最小的是哪一个？它距离 $s$ 有多远？

如果存在从 $s$ 无法到达的补给站，请输出 Impossible。

输入格式

第一行包含三个整数 $n, m, s$。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示站点 $u$ 和站点 $v$ 之间有一条双向山路。

输出格式

如果所有站点都可达，输出两个整数，分别表示：

• 编号最小的最远补给站编号
• 它到 $s$ 的距离

如果存在不可达站点，输出 Impossible。

输入输出样例 #1

输入 #1

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

输出 #1

3 2

输入输出样例 #2

输入 #2

5 2 2
1 2
4 5

输出 #2

Impossible

数据范围

对于 $50\%$ 的数据，$1 \le n \le 1000$，$0 \le m \le 5000$。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le m \le 2 \times 10^5$。

建议

一刷、二刷