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.
Cerinţă
Determinaţi distanţa minimă dintre două case distincte dintre cele X din cartier.
Date de intrare
Pe prima linie a fişierului de intrare reinvent.in se află trei numere întregi N M 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
Exemple
reinvent.in
reinvent.out
Explicaţii
5 6 2
1 2
2 3
2 4
3 4
1 4
3 5
1 5
3
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.