== include(page="template/taskheader" task_id="evacuare") ==

Poveste şi cerinţă...

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 $Pi$ 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 $Pi$ se poate evacua prin încăperea $k$ şi există un tunel direct între încăperile $i$ şi $Pi$.
 
	Î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 $Pi$. Un semn dintr-o încăpere $i$ trebuie schimbat dacă numărul $Pi$ î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$.
 

h2. Date de intrare

Fişierul de intrare $evacuare.in$ ...

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 $Pi$ înscris pe semnul aflat în camera $i$.

h2. Date de ieşire

În fişierul de ieşire $evacuare.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu