Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Keskukset

Keskukset


View task | Model solution | Statistics


Keskukset

Time limit:1.00 s
Memory limit:128 MB

Bittimaassa on $n$ kaupunkia, ja tiedät jokaisen kaupungin asukasluvun. Kaupunkien välille aletaan rakentaa metroyhteyksiä. Keskus on joukko kaupunkeja, jossa mistä tahansa kaupungista toiseen pääsee metrolla.

Tehtäväsi on ilmoittaa jokaisen yhteyden rakentamisen jälkeen, kuinka monta asukasta asuu suurimmassa keskuksessa.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: kaupunkien määrä ja yhteyksien määrä. Kaupungit on numeroitu $1,2,\ldots,n$.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$: kunkin kaupungin asukasluku.

Lopuksi syötteessä on $m$ riviä, jotka kuvaavat rakennettavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: kaupunkien $a$ ja $b$ välille rakennetaan yhteys. Kaikki yhteydet ovat kaksisuuntaisia.

Tuloste

Ohjelmasi tulee tulostaa jokaisen yhteyden rakentamisen jälkeen suurimman keskuksen asukasluku.

Rajat
Esimerkki

Syöte:
4 4
5 3 7 9
1 2
1 3
2 3
3 4


Tuloste:
9 15 15 24