SP4097 MTRAIN - Locomotive

题目描述

Mirko 和 Slavko 终于在克罗地亚铁路公司找到了火车司机的工作。然而，任务来了。每人需要从一个特定的城镇出发，尽可能访问更多的城镇。

Mirko 已经积累了丰富的经验，无所畏惧。然而，Slavko 则是第一次开火车，单独操作还不太熟练。好在火车都配备了无线电，这样 Slavko 只要在 Mirko 的无线电范围内，就可以按照他的指令正常行驶。

给定平面上的 $N$ 个城镇，其中一些通过铁路连接。Mirko 和 Slavko 从不同的城镇出发，并且在任何时刻，他们之间的距离都不能超过 $D$ 公里。

火车可以在任意速度和方向上沿铁路行驶，并且只能在城镇中进行轨道切换。确保 Mirko 和 Slavko 在行驶过程中，彼此的距离不会超过 $D$ 公里。

你的任务是编写程序，找出 Slavko 可以到达的所有城镇编号。

输入格式

第一行输入包括三个数：$N$（城镇数）、$P$（铁路数）和 $D$（无线电有效范围，带有两位小数），其中 $2 \le N \le 100$, $1 \le P \le 3000$, $1 \le D \le 10,000$。这些城镇的编号为 1 到 $N$。接下来 $N$ 行，每行两个整数 $X$ 和 $Y$，表示城镇的坐标，范围是 $-5000 \le X, Y \le 5000$。

接下来的 $P$ 行，每行有两个整数 $G_1$ 和 $G_2$，表示有一条铁路连接城镇 $G_1$ 和 $G_2$。

最后一行包括两个整数 $U$ 和 $V$，表示 Mirko 从城镇 $U$ 开始，Slavko 从城镇 $V$ 出发。保证 $U$ 和 $V$ 之间的距离不超过 $D$ 公里。

输出格式

输出 Slavko 可以到达的所有城镇编号，以升序排列，每行输出一个编号。

5 4 1.5
0 1
0 0
4 1
4 0
2 2
1 3
1 5
3 5
2 4
2 1

1
3

说明/提示

$$2 \le N \le 100, \quad 1 \le P \le 3000, \quad 1 \le D \le 10,000.$$

本翻译由 AI 自动生成