- Time limit: 1.00 s
- Memory limit: 128 MB
Syrjälässä on tietokonetta, joiden välillä on yhteyttä. Koneet muodostavat aliverkkoja niin, että jokainen aliverkko sisältää kaikki koneet, joihin pystyy olemaan yhteydessä toisistaan.
Syrjälässä ei ole ketään, joka ymmärtäisi verkon toimintaa. Niinpä jos koneiden välinen yhteys katkeaa, kukaan ei korjaa sitä. Yhteyden katkeamisen seurauksena jokin aliverkko saattaa jakautua kahdeksi aliverkoksi.
Tehtäväsi on laskea aliverkkojen määrä kunkin yhteyden katkeamisen jälkeen.
Syöte
Syötteessä on ensin kolme kokonaislukua , ja : koneiden määrä, yhteyksien määrä ja katkeamisten määrä. Koneet on numeroitu .
Sitten syötteessä on riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua ja : koneiden ja välillä on yhteys. Kaikki yhteydet ovat kaksisuuntaisia. Koneesta ei voi olla yhteyttä itseensä, ja jokaisen kahden koneen välillä on enintään yksi yhteys.
Lopuksi syötteessä on riviä, jotka kuvaavat katkeamiset. Jokaisella rivillä on kaksi kokonaislukua ja : koneiden ja välinen yhteys katkeaa.
Tuloste
Tulosta jokaisen katkeamisen jälkeen aliverkkojen määrä.
Rajat
Esimerkki
Syöte:
5 5 3 1 2 1 3 2 3 3 4 4 5 3 4 2 3 4 5
Tuloste:
2 2 3