Powder s-a strecurat în biroul lui Jayce din Piltover pentru a șterpeli tehnologie avansată, și acum dorește să ajungă înapoi în Zaun. Din păcate, multe intersecții din Piltover sunt pline de polițiști investigând diferite fărădelegi. Ea știe că va fi prinsă dacă trece prin cel puțin 3 intersecții cu polițiștii (a 3-a oară e cu ghinion), și dorește să ajungă cât mai repede la intrarea secretă către orașul subteran Zaun. Știind că harta orașului este codificată prin N numere (de la 1 la N) reprezentând intersecțiile, și prin M perechi de numere (reprezentând o stradă prin numerele de ordine ale intersecțiilor din capetele străzii), aflați următoarele informații:
1. Numărul minim de intersecții prin care trece Powder pentru a ajunge la intrarea în Zaun de la biroul lui Jayce
2. În cazul în care sora lui Powder, numită Vi, reușește să ademenească toți polițiștii în intersecția cu numărul de ordine V, care este cel mai scurt drum (ca număr de intersecții) pe care Powder trebuie să îl parcurgă ca să ajungă la intrarea în Zaun de la biroul lui Jayce, dacă nu are voie să ajungă în intersecția V (ar fi prinsă de polițiștii de acolo)? Evident, în celelalte intersecții nu se mai regăsesc polițiști (au plecat toți la intersecția V în acest caz).
Se vor afla pe prima linie 4 numere N, M, K, V, reprezentând numărul de intersecții, numărul de străzi, numărul de polițiști și intersecția specială în care vor fi ademeniți polițiștii la subpunctul 2) . Pe următoarele M linii se va afla câte o pereche de numere de la 1 la N, această pereche reprezentând strada respectivă, iar după acestea se vor afla pe o singură linie cele K intersecții în care se află inițial polițiștii.
Se vor afișa două numere separate prin spațiu, primul fiind răspunsul la subpunctul 1), iar al doilea la subpunctul 2) .
Pentru 20 de puncte, numărul de polițiști va fi < 3
Pentru alte 20 de puncte, numărul de polițiști va fi <= 10 și N, M <= 1000
Pentru alte 20 de puncte, N, M <= 4000
Pentru alte 20 de puncte, N, M <= 30000
Pentru restul de 20 de puncte nu vor exista restricții adiționale.
Pentru fiecare test, dacă se răspunde corect la o singură cerință, veți primi jumatate din valoarea testului dacă sunt afișate două numere în fișierul de intrare, în ordinea corectă.
9 10 4 6 1 2 1 3 2 4 3 5 5 6 5 7 7 8 6 9 8 9 4 5 3 5 6 7
6 6
Biroul lui Jayce este considerat ca fiind intersecția 1, iar intrarea în Zaun intersecția cu numărul N.
1 <= N, M <= 100000
În cazul în care nu este posibilă realizarea unui drum corect la vreo cerință, se va afișa -1 pentru subtaskul respectiv.
