Fişierul intrare/ieşire:reinvent.in, reinvent.outSursăONI 2009, clasele 11-12
AutorMircea Bogdan PasoiAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Reinvent

Zăhărel şi Sică s-au gândit să se reinventeze din punct de vedere spiritual. În prima fază, vor să se mute în oraşul Sala. Oraşul Sala conţine N case (numerotate de la 1 la N) unite prin M străzi bidirecţionale de lungimi egale. Ei au la dispoziţie fonduri limitate şi pot să se mute doar într-un cartier mărginaş format din X case. Fiindcă sunt buni prieteni cei doi vor să se mute în două case distincte, cât mai apropiate între ele.

Determinaţi distanţa minimă dintre două case distincte din cele X din cartier.

Date de intrare

Pe prima linie a fişierului de intrare reinvent.in se află trei numere întregi N, M si X separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii se află câte două numere întregi distincte separate printr-un singur spaţiu, reprezentând o stradă bidirecţională din oraş. Ultima linie din fişier conţine X numere naturale distincte separate prin câte un spaţiu, reprezentând casele din cartier.

Date de ieşire

În fişierul de iesire reinvent.out se află un singur număr natural, reprezentând distanţa minimă între două case distincte din cartier.

Restricţii

  • 1 ≤ N, M ≤ 100.000
  • 2 ≤ X ≤ N
  • Pentru 30% din teste N ≤ 1024
  • Distanţa între două case se măsoară prin numărul minim de străzi necesare pentru a ajunge de la o casă la cealaltă
  • Între oricare două case există cel mult o stradă bidirecţională.
  • Există cel puţin două case din cartier astfel încât să existe drum între ele

Exemplu

reinvent.inreinvent.out
5 6 2
1 2
2 3
2 4
3 4
1 4
3 5
1 5
3

Explicaţie

Distanţa minimă între casele 1 şi 5 din cartier este 3. Un drum posibil format din 3 străzi este 1235.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content