Question

Enunț
În țara Zoomba trăiesc K prieteni, fiecare în localități diferite. În această țară se găsesc N orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei K prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă 1 litru de benzină.

Cerința
Știind că odată ce au ajuns în același oraș 2 sau mai mulți prieteni, aceștia iși pot continua drumul cu o singură mașină, să se determine consumul minim de benzină pentru ca aceștia să ajungă în orașul Z.

Date de intrare
Fișierul de intrare zoomba.in conține pe prima linie numerele N, M(numărul de șosele), K și Z. Pe următoarea linie se află K numere, reprezentând pozițiile inițiale ale celor K prieteni. Pe următoarele M linii se află câte o pereche i j, cu semnificația că există șosea de la orașul i la orașul j.

Date de ieșire
Fișierul de ieșire zoomba.out va conține pe prima linie numărul C, ce va fi egal cu consumul minim de combustibil necesar ca cei K prieteni să se întâlnească în orașul Z, sau -1 în cazul în care aceștia nu pot ajunge în el.

Restricții și precizări
1 ≤ Z ≤ N ≤ 200
1 ≤ K ≤ min(N,10)



Exemplu
zoomba.in

5 4 3 5
1 2 3
1 4
2 4
3 4
4 5
zoomba.out

4

Answer 1

Ti-am atasat programul sursa C++

d4092e6ddd693793f3b418f6c2c8491a.cpp