== include(page="template/taskheader" task_id="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.
Poveste şi cerinţă...
h2. 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.
Fişierul de intrare $reinvent.in$ ...
h2. 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.
În fişierul de ieşire $reinvent.out$ ...
h2. 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
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. reinvent.in |_. reinvent.out |
| 5 6 2
1 2
2 3
2 4
3 4
1 4
3 5
1 5
| 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Distanţa minimă între casele $1$ şi $5$ din cartier este $3$. Un drum posibil format din $3$ străzi este $1$ – $2$ – $3$ – $5$.
...
== include(page="template/taskfooter" task_id="reinvent") ==
