cangrena

Orașul TownsVille este un oraș foarte aglomerat. Acesta este format din $N$ intersecții numerotate de la $1$ la $N$, conectate prin $M$ străzi. Primarul orașului cunoaște pentru câteva din cele $N$ intersecții un coeficient pozitiv $A[i]$ reprezentând aglomerația din intersecția $i$. Pentru intersecțiile în care acest coeficient este necunoscut, primarul este obligat să fixeze personal acest coeficient (de asemenea pozitiv).

Inițial, primarului nu prea îi păsa ce coeficienți selectează. Dacă pentru o intersecție coeficientul era prea mic, lumea ar fi fost mulțumită, dacă nu, ar fi impus taxe, deci el ar fi fost mulțumit. Din păcate, Gașca Cangrenă este pusă pe tot felul de mârlănii: de la aruncat hârtie în coșul cu plastic, până la furat înghețata copiilor mici, orice e posibil. Astăzi, în schimb, aceștia s-au decis să fure cauciucurile mașinilor din interiorul intersecțiilor. Astfel, primarul și-a impus următoarea regulă: pentru oricare două intersecții conectate printr-o stradă, diferența coeficientului de aglomerație între cele două intersecţii trebuie să nu fie prea mare. Dacă această diferență ar fi mult prea mare, Gașca Cangrenă ar ataca cu siguranță intersecția mai aglomerată. Altfel, aceștia ar fi confuzi pe care să o atace (întrucât nu știu să numere câte mașini sunt într-o intersecție), fapt care le-ar câștiga timp fetițelor Powerpuff să vină să salveze situația.

Dându-se configurația orașului TownsVille, precum și coeficienții cunoscuți de aglomerație ai unor intersecții, scopul vostru este să selectați câte un coeficient de aglomerație pentru restul intersecțiilor astfel încât să minimizați diferența maximă între oricare două intersecții conectate printr-o stradă.

Date de intrare

Fișierul de intrare cangrena.in va conține pe prima linie două numere naturale $N$ și $M$, cu semnificația din enunț. Pe următoarea linie se vor afla $N$ numere, al $i$-lea număr reprezentând coeficientul de aglomerație al intersecției numerotate cu indicele $i$, dacă acest coeficient este cunoscut, $-1$ altfel. Următoarele $M$ linii vor conține câte două numere naturale $A$ și $B$, reprezentând faptul că intersecția $A$ este conectată cu intersecția $B$ printr-o stradă.

Date de ieşire

Fișierul de ieșire cangrena.out va conține o singură linie cu $N$ numere naturale pozitive (separate prin cate un spațiu), al $i$-lea număr reprezentând coeficientul de aglomerație al intersecției cu indicele $i$ (se vor afișa inclusiv coeficienții fixați inițial).

Restricţii şi precizări

• $2 ≤ N ≤ 100\ 000$
• $1 ≤ M ≤ 200\ 000$
• din orice intersecţie se poate ajunge în oricare alta prin drumurile existente
• există cel puţin o intersecţie cu coeficientul de aglomeraţie cunoscut
• în orice intersecţie ajunge cel puţin o stradă
• străzile sunt bidirecţionale
• coeficienţii de aglomerare cunoscuţi sunt numere naturale nenule mai mici sau egale cu $1\ 000\ 000\ 000$

Exemplu

cangrena.in

4 3
10 -1 20 12
1 2
2 3
4 2

cangrena.out

10 15 20 12

cangrena.in

8 8
-1 33 -1 -1 -1 -1 -1 31
1 3
1 6
2 5
3 8
4 8
5 6
5 7
6 7

cangrena.out

33 33 32 32 34 34 35 31

Explicaţii