题目描述

Mirko和Slavko终于找到了工作——火车司机。第一天上班，他们就接到一个任务：各从一个给定的城市出发，访问尽可能多的城市。 Mirko是个有经验的司机，他什么都不怕。但是Slavko是个新手，如果只有他一个人，他什么都做不了。幸运的是，火车上有无线电收发装置，所以只要Slavko处在Mirko驾驶的火车的通讯范围内，就可以根据Mirko的指令顺利驾驶了。 N座城市处于一个平面上，有的城市之间有铁路相连。Mirko和Slavko从不同的城市出发，他们之间的距离不超过D千米。 火车可以在所有的铁路上以任意速度沿着任意方向行驶。火车不能在非城市的地方更换铁路。在任意时刻，Mirko和Slavko的距离都不能超过D千米。 请你写一个程序，列出Slavoko可能到达的所有城市。

输入格式

第一行有两个整数N和P，一个实数D，2<=N<=100，1<=P<=3000。N是城市的数目，P是铁路的数目，D是无线电收发装置的最大通讯距离（以千米为单位，保留两位小数）。城市编号从1到N。 接下来的N行，每行两个整数X和Y，-5000<=X,Y<=5000，表示城市的位置。 接下来的P行，每行两个整数G1和G2，表示有一条铁路连接G1和G2。 最后一行有两个整数U和V，分别表示Mirko和Slavko的出发城市。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

提示

没有写明提示

题目来源

没有写明来源