- Time limit: 1.00 s
- Memory limit: 128 MB
Bittimaassa on 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 ja : kaupunkien määrä ja yhteyksien määrä. Kaupungit on numeroitu .
Seuraavalla rivillä on kokonaislukua : kunkin kaupungin asukasluku.
Lopuksi syötteessä on riviä, jotka kuvaavat rakennettavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua ja : kaupunkien ja 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
Esimerkki
Syöte:
4 4 5 3 7 9 1 2 1 3 2 3 3 4
Tuloste:
9 15 15 24