A. Heist
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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).

Input

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.

Output

Se vor afișa două numere separate prin spațiu, primul fiind răspunsul la subpunctul 1), iar al doilea la subpunctul 2) .

Scoring

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ă.

Example
Input
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
Output
6 6
Note

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.