cangrena

Cangrena

!{width: 300px; float: right; margin: 10px}problema/cangrena?main.png!

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

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.

h2. 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ă.

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

h2. Date de ieşire

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

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

h2. Restricţii

* *2 ≤ N ≤ 100 000*
* *1 ≤ M ≤ 200 000*

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

* coeficienţii de aglomerare *cunoscuţi* sunt numere naturale nenule mai mici sau egale cu $1.000.000.000$

h2. Exemplu