Walkie-talkie

Limit pamięci: 64 MB

Mirek i Sławek zostali niedawno zatrudnieni jako maszyniści w PKP. Już pierwszego dnia pracy dostali ciekawe zadanie. Każdy z nich powinien wystartować ze wcześniej ustalonego miasta i przejechać swoją lokomotywą przez jak największą liczbę miast.

Mirek ma już doświadczenie w prowadzeniu pociągu, więc nie boi się niczego. Dla Sławka jest to jednak pierwszy raz, więc nie potrafi nic samodzielnie zrobić z pociągiem. Szczęśliwie, wszystkie lokomotywy są wyposażone w walkie-talkie, więc Mirek może instruować Sławka, tak długo jak pozostają oni w zasięgu działania tego urządzenia.

Miasta są reprezentowane przez punkty na płaszczyźnie. Niektóre z nich połączone są torami kolejowymi, czyli odcinkami łączącymi dane punkty. Mirek i Sławek zaczynają swoją podróż w miastach oddalonych od siebie o co najwyżej kilometrów.

Lokomotywy mogą jeździć po torach w dowolnym kierunku i z dowolną prędkością (także robić postoje w dowolnych miejscach), ale zmieniać tor którym jadą jedynie w miastach. Mirek i Sławek w każdym momencie muszą być w odległości co najwyżej kilometrów.

Napisz program, który znajdzie wszystkie miasta, które może odwiedzić Sławek, zgodnie z zasadami opisanymi powyżej.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sieci kolejowej, liczbę oraz pozycje startowe Mirka i Sławka,
• znajdzie miasta, do których może dojechać Sławek
• zapisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera liczby całkowite i (, ) oraz liczbę rzeczywistą (, ma co najwyżej dwie cyfry po przecinku). Oznaczają one, odpowiednio: liczbę miast, liczbę odcinków torów oraz zasięg walkie-talkie w kilometrach. Miasta są ponumerowane liczbami od do . Każdy z kolejnych wierszy zawiera współrzędne miasta na mapie , (). Kolejne wierszy opisuje sieć kolejową. W każdym z nich znajdują się dwie liczby całkowite - numery miast połączonych odcinkiem torów.

Ostatnia linia zawiera numery miast w których zaczynają swoją podróż Mirek i Sławek, w tej kolejności. Te dwa miasta nie są odległe o więcej niż kilometrów.

Wyjście

Wyjście powinno składać się z numerów miast, do których może dotrzeć Sławek. Numery te powinny być posortowane rosnąco i wypisane po jednej liczbie na wiersz.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

1
3

Zapożyczenie z chorwackiej olimpiady informatycznej: Tomasz Kulczyński.