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.