Nosaukums
Lokomotīvju radio (lokomot)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

Mirko un Slavko beidzot ir dabūjuši lokomotīvju vadītāju darbu uz Horvātijas dzelzceļa. Jau pirmajā darba dienā viņi ir saņēmuši uzdevumu - paņemt savas lokomotīves noteiktā pilsētā un apciemot pēc iespējas daudz citas pilsētas.

Mirko ir pieredzējis vadītājs, tāpēc viņam šāds uzdevums raizes nesagādā. Savukārt, Slavko šis būs pirmais brauciens vienam pašam un viņš ir mēreni nobijies. Par laimi, abām lokomotīvēm ir rācijas un ja lokomotīves neatrodas pārāk tālu viena no otras, tad Slavko var sazināties ar Mirko un saņemt atbildes uz jautājumiem.

Ir N pilsētas, kuru atrašanās vietas plaknē ir zināmas. Dažas pilsētas savieno taisna dzelzceļa līnija. Mirko un Slavko sāk savus braucienus divās dažādās pilsētās kas atrodas ne tālāk kā D kilometrus viena no otras.

Lokomotīves drīkst lietot jebkuru dzelzceļu, braukt pa to jebkurā virzienā un ar jebkuru ātrumu. Lokomotīves var pārbraukt no viena dzelzceļa uz otru tikai pilsētās. Mirko un Slavko vadītās lokomotīves katrā laika momentā nedrīkst atrasties tālāk kā D kilometrus.

Uzrakstiet programmu, kas nosaka visas tās pilsētas, kurās Slavko ar savu lokomotīvi var ierasties!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas naturāla skaitļa N, naturāla skaitļa P un reāla skaitļa D vērtības, kas atdalītas ar tukšumsimbolu. N ir pilsētu skaits (2≤N≤100), P ir dzelzceļu skaits (1≤P≤3000) un D ir rācijas darbības attālums (1≤D≤10000). D būs uzdots ar ne vairāk kā divām decimālajām zīmēm aiz komata. Pilsētas ir sanumurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas.

Katra no nākošajām N faila rindām ir dotas vienas pilsētas koordinātas X un Y, kas atdalītas ar tukšumsimbolu. Zināms, ka -5000≤X,Y≤5000. Faila i+1-ajā rindā ir dotas i-tās pilsētas koordinātas (1≤i≤N).

Katra no nākošajām P rindām apraksta vienu dzelzceļa posmu, norādot tā galapunktos esošās pilsētas.

Nākošajā faila rindā doti divi naturāli skaitļi U un V, kas atdalīti ar tukšumsimbolu. Mirko sāk braucienu pilsētā U, bet Slavko - pilsētā V. U un V ir divas pilsētas, attālums starp kurām nepārsniedz D kilometrus.


Izvaddatu raksturojums

Izvaddatos jāizvada visu to pilsētu numuri, kurās Slavko var ierasties. Pilsētas numuri jāizvada augošā secībā, pa vienam numuram katrā rindā.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
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
Stdout
1
2
3
4

Stdin
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
Stdout
5
6
7
8

Stdin
5 4 1.5
0 1
0 0
4 1
4 0
2 2
1 3
1 5
3 5
2 4
2 1
Stdout
1
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.