Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Jei norite pateikti savo sprendimą - prisijunkite.

Vamzdžiai (BOI 2013)

Hotamo miestas vėl puolamas paties pavojingiausio blogiečio Pokštininko. Jo taikinys yra Hotamo vandentiekis. Šviežias vanduo laikomas vamzdžiais sujungtose talpose. Iš viso yra N talpų ir M vamzdžių, ir keliaujant vamzdžiais galima patekti iš bet kurios talpos į bet kurią kitą. Be to, tarp bet kurios poros talpų nutiestas daugiausia vienas vamzdis ir nėra vamzdžių, einančių iš talpos į ją pačią. Pokštininkas pramušė kai kuriuos vamzdžius ir iš jų leidžia vandenį. Iš vamzdžio išleidžiamas sveikasis lyginis skaičius kubinių metrų per sekundę (m^3/s) vandens. Jei 2dm^3/s vandens išleidžiama iš vamzdžio, jungiančio talpas u ir v, tai u ir v abu praranda po dm^3/s vandens. Norėdamas suklaidinti miestiečius, Pokštininkas į kai kuriuos vamzdžius pompuoja vandenį, vietoje to, kad jį išleistų. Į vamzdį įpompuojamas taip pat lyginis skaičius m^3/s vandens. Jei 2pm^3/s vandens įpompuojama į vamzdį, jungiantį talpas u ir v, tai u ir v gauna po pm^3/s vandens. Kiekvienos talpos vandens tūrio bendras kitimas yra suma visų praradimų ir gavimų, patiriamų dėl iš talpos einančių vamzdžių. Tiksliau, jei iš talpos eina vamzdžiai, iš kurių išsiurbama 2d_1,2d_2,...,2d_am^3/s vandens ir vamzdžiai, į kuriuos įpompuojama 2p_1,2p_2,...,2p_bm^3/s vandens, tai tos talpos bendras kitimas yra p_1+p_2+...+p_b-d_1-d_2-...-d_a. Hotamo meras įdiegė daviklius talpose, bet ne vamzdžiuose. Taigi jis mato bendrus kitimus visose talpose, bet nežino, kiek vandens išleidžiama ir įpompuojama į vamzdžius. Parašykite programą, kuri padėtų merui. Turėdama visą informaciją apie vandentieko tinklą ir bendrus kitimus talpose, jūsų programa turi nustatyti, ar šios informacijos pakanka vienareikšmiškai nustatyti Pokštininko planą. Planas nustatomas vienareikšmiškai, jei kiekvienam vamzdžiui yra lygiai viena galimybė, kiek vandens iš jo išleidžiama ar į jį įpompuojama. Atkreipkite dėmesį, kad šie kiekiai nebūtinai sutampa visiems vamzdžiams. Jei yra lygiai vienas galimas planas, jūsų programa turi jį pateikti.

Pradiniai duomenys

Pirmoje eilutėje pateikiami du sveikieji skaičiai: talpų skaičius N ir vamzdžių skaičius M. Kitose N eilučių yra po vieną sveikąjį skaičių c_i — vandens tūrio kitimą talpoje i (1\\leqi\\leqN). Iš šių N eilučių, i-oje yra skaičius c_i. Po to M eilučių pateikiama po du sveikuosius skaičius u_i ir v_i (1\\leqi\\leqM,1\\lequ_i,v_i\\leqN). Kiekviena tokia eilutė reiškia, kad tarp talpų u_i ir v_i yra nutiestas vamzdis. Iš šių M eilučių, i-oje yra skaičiai u_i ir v_i. Duomenys tokie, visuomet bus bent vienas galimas Pokštininko planas.

Rezultatai

Jei Pokštininko planas negali būti nustatytas vienareikšmiškai, vienintelėje eilutėje turi būti išvestas 0. Kitu atveju reikia patekti M eilučių, i-oje pateikiant sveikąjį skaičių x_i (1\\leqi\\leqM). Jei Pokštininkas išleidžia d_im^3/s vandens iš u_i ir v_i jungiančio vamzdžio, tai x_i=-d_i. Jei Pokštininkas įpumpuoja p_im^3/s vandens į vamzdį tarp u_i ir v_i , tai x_i=p_i. Jei Pokštininkas nieko nedaro su šiuo vamzdžiu, tai x_i=0.

Ribojimai

1\\leqN\\leq100000, 1\\leqM\\leq500000, -10^9\\leqc_i\\leq10^9.

Jei Pokštininko planas gali būti nustatytas vienareikšmiškai, tai -10^9\\leqx_i\\leq10^9.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4 3
-1
1
-3
1
1 2
1 3
1 4
 
2
-6
2
 
4 5
1
2
1
2
1 2
2 3
3 4
4 1
1 3
 
0