Fișierul intrare/ieșire	evacuare.in, evacuare.out	Sursă	Lot Sovata 2014
Autor	autor necunoscut	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	1.1 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Evacuare (lot liceu)

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

• Încăperea i este chiar camera care conține ieșirea (i = k).
• Î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șierul 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

În 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

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

Exemplu

Explicație

Pentru a evacua salina prin încăperea 1, va trebui să schimbăm numărul P₂ din 3 în 1 și P₃ 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₄ î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.