MTRAIN - Locomotive

no tags 

Mirko and Slavko have finally gotten jobs as locomotive drivers on the Croatian Railroad. As early as the first day of work, they got an assignment. Each of them was to take their locomotive from a certain town and visit as many towns as possible.

Mirko is an experienced driver, so he is afraid of nothing. This was, however, Slavko’s first train ride and he can do absolutely nothing by himself. Luckily, all the locomotives have radios, so Slavko can drive the locomotive normally as long as he is within the range of Mirko’s radio to give him instructions.

N towns have been given in a coordinate plane. Some of the towns are connected by railroad. Mirko and Slavku start their tour in different towns, and so that they are at most D kilometers away from each other.

The locomotives can use all railroads, at any speed and in any direction. Locomotives can switch railroad tracks in towns only. Mirko and Slavko may be at most D kilometers away from each other at any moment in time.

Write a program that will determine all possible towns that Slavko can visit, as was described above.

Input

The first line of the input file contains the numbers N and P, and a real number D, 2 ≤ N ≤ 100, 1 ≤ P ≤ 3000, 1 ≤ D ≤ 10,000. The number N is the number of towns, the number P is the number of railroads, and D is the range of the radio in kilometers (a decimal number two digits precise). The towns are numbered 1 to N. Each of the following N lines contains data describing one town, i.e. two integers, X and Y, -5000 ≤ X, Y ≤ 5000, representing the town’s coordinates.

Each of the following P lines contains data describing one railroad track, i.e. two integers G1 and G2, saying there is a railroad track connecting G1 i G2.

The next line contains the starting positions of Mirko and Slavku, the integers U and V. Mirko starts from town U, Slavko from town V. U and V will represent two towns separated at most D kilometers in distance.

Output

The output file should contain the numbers of all the towns Slavko can reach. These numbers should be sorted in increasing order, each of them written on a separate line.

Sample

Input:
5 4 1.5
0 1
0 0
4 1
4 0
2 2
1 3
1 5
3 5
2 4
2 1

Output:
1
3
Input:
8 6 4
0 0
4 3
8 0
16 0
0 -1
8 -1
12 -4
16 -1
1 2
2 3
3 4
5 6
6 7
7 8
1 5

Output:
5
6
7
8
Input:
8 6 2
0 0
1 0
2 0
1 1
0 1
1 3
2 1
1 -10
1 2
2 4
2 3
5 6
6 7
2 8
5 1

Output:
1
2
3
4

hide comments
Hussain Kara Fallah: 2012-07-13 01:53:09

Can Mirko stay in a city and Slavko go to another (and their far is less than D)????

Abdul Baset Al-Joudy: 2011-09-07 10:22:08

Should we read / write from the mentioned files, or from / to stdin / stdout?
Edit: NVM, I was dumb.

Last edit: 2012-03-12 10:56:05
[Trichromatic] XilinX: 2009-11-28 13:38:21

:) Be careful with the REAL data constraints :) That is:
2 <= N <= 60, 1 <= P <=80.
Ha ha ha ha!!!


Added by:psetter
Date:2009-03-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 03