CSES - Keskukset
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Bittimaassa on nn 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 nn ja mm: kaupunkien määrä ja yhteyksien määrä. Kaupungit on numeroitu 1,2,,n1,2,\ldots,n.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: kunkin kaupungin asukasluku.

Lopuksi syötteessä on mm riviä, jotka kuvaavat rakennettavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: kaupunkien aa ja bb välille rakennetaan yhteys. Kaikki yhteydet ovat kaksisuuntaisia.

Mikään yhteys ei ole kaupungista itseensä, ja kahden kaupungin välille rakennetaan enintään yksi yhteys.

Tuloste

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

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1xi1091 \le x_i \le 10^9
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

4 4
5 3 7 9
1 2
1 3
2 3
3 4

Tuloste:

9 15 15 24