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

Poveste şi cerinţă...

Okabe are de descifrat un nou mister. Pentru a realiza acest lucru, el trebuie sa afle riscul de a forma un paradox in fiecare linie a timpului in care acesta se afla. Mai exact, fie un graf cu $N$ noduri si $M$ muchii ORIENTATE(nodurile reprezinta stari in timp si muchiile relatii intre aceste stari, fapt irelevant). Pentru fiecare nod $X$ se cunoaste o valoare $risc[X]$ la evenimentul $0$. La fiecare eveniment, riscul dintr-un nod $X$ se propaga in toti vecinii acestuia (daca exista muchie de la $X$ la $Y$). Deoarece universul este complicat, riscul unui nod devine dupa fiecare moment, maximul valorilor care se propaga in acest nod. Misiunea lui Okabe este sa afle riscul din fiecare nod dupa $K$ evenimente.

h2. Date de intrare

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

Fişierul de intrare $steinsgate.in$ va contine pe prima linie $3$ numere naturale $N$, $M$ si $K$. Pe urmatoarele $M$ linii se afla cate $2$ numere naturale $X$ si $Y$ reprezentand faptul ca avem muchie de la $X$ la $Y$. Pe ultima linie vor fi $N$ numere naturale, elementul al $i$-lea reprezentand riscul nodului $i$ la evenimentul $0$.

h2. Date de ieşire

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

Fişierul de ieşire $steinsgate.out$ va contine o singura linie cu $N$ numere naturale reprezentand riscul fiecarui nod dupa $K$ evenimente.

h2. Restricţii

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

* $1 ≤ N ≤ 200$
* $$ ≤ M ≤ N * N$
* $1 ≤ risc[i] ≤ 1.000.000.000$

h2. Exemplu