Evacuare

Ca să ia o binemeritată pauză de la curățenie, Hetty s-a dus în excursie la Praid, ca să viziteze salina din oraș. Aceasta este formată din $N$ încăperi legate între ele prin $M$ tuneluri bidirecționale. Hetty a observat că în fiecare încăpere $i \ (1≤i≤N)$ a fost plasat un semn pe care este scris numărul $P_i$ al încăperii spre care trebuie să se îndrepte vizitatorii în cazul unei evacuări de urgență. Astfel, spunem că o încăpere $i$ poate fi evacuată printr-o încăpere $k$ dacă și numai dacă una din
următoarele propoziții este adevărată:

1. Încăperea $i$ este chiar camera care conține ieșirea $(i=k)$
2. Încăperea $P_i$ se poate evacua prin încăperea $k$ și există un tunel direct între încăperile $i$ și $P_i$.

În acest moment se știe că toate încăperile din salină pot fi evacuate prin camera $X$. Acest lucru este însă pe cale să se schimbe, întrucât proprietarii salinei doresc să închidă ieșirea din încăperea $X$ și să deschidă o alta într-o încăpere $Y$. Întrucât salina să poată fi redeschisă, proprietarii trebuie să schimbe unele dintre semnele $P_i$. Un semn dintr-o încăpere $i$ trebuie schimbat dacă numărul $P_i$ înscrisă pe el trebuie modificat pentru ca încăperea $i$ să poată fi evacuată prin încăperea $Y$. Hetty se întreabă acum care este numărul minim de semne care trebuie schimbate pentru a putea evacua toate încăperile salinei prin încăperea $Y$, pentru fiecare $Y$ între $1$ și $N$.

Date de intrare

Fișierului de intrare evacuare.in conține pe prima linie $3$ numere naturale, $N, M,$ și $X$ reprezentând numărul de încăperi, numărul de tunele din salină, respectiv camera care conține inițial ieșirea. Pe următoarele $M$ linii se vor afla câte două numere naturale, reprezentând o pereche de camere care sunt unite printr-un tunel direct. Pe ultima linie se vor afla $N$ numere naturale. Al $i$-lea dintre acestea reprezintă numărul $P_i$ înscris pe semnul aflat în camera $i$.

Date de ieșire

In fișierul de ieșire evacuare.out se vor afișa $N$ linii. Linia $i$ va conține numărul minim de semne care trebuiesc schimbate pentru ca salina să poată fi evacuată prin camera $i$.

Restricții și precizări

• $2 ≤ N ≤ 500 \ 000$
• $1 ≤ M ≤ 600 \ 000$
• Pentru $20\%$ din teste $M = N-1$.
• Pentru $30\%$ din teste $2 ≤ N ≤ 2 \ 000$
• Nu există un tunel care să lege o cameră de ea însăși.

Exemplu

evacuare.in

4 4 3
1 2
2 3
2 4
3 4
2 3 4 3

evacuare.out

2
1
0
0

Explicație

Pentru a evacua salina prin încăperea $1$, va trebui să schimbăm numărul $P_2$ din $3$ în $1$ și $P_3$ din $4$ în $2$.

Astfel, putem evacua cele $4$ încăperi pe rutele:

• $1: 1$
• $2: 2 → 1$
• $3: 3 → 2 → 1$
• $4: 4 → 3 → 2 → 1$

Observăm că am putea schimba și $P_4$ în $2$ pentru a evacua încăperea $4$ pe ruta $4 → 2 → 1$ însă această variantă nu duce la număr minim de semne schimbate.