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ța

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

Fișierul de ieșire reinvent.out va conține un singur număr natural, reprezentând distanţa minimă între două case distincte din cartier.

Restricții și precizări

• 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.in

5 6 2
1 2
2 3
2 4
3 4
1 4
3 5
1 5

reinvent.out

3

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.