Code Submission Evaluation System Login

Datatähti-valmennus

Aliverkot


Task | Statistics


CSES - Aliverkot

Time limit:1.00 s Memory limit:128 MB

Syrjälässä on $n$ tietokonetta, joiden välillä on $m$ 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 $n$, $m$ ja $k$: koneiden määrä, yhteyksien määrä ja katkeamisten määrä. Koneet on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: koneiden $a$ ja $b$ 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 $k$ riviä, jotka kuvaavat katkeamiset. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: koneiden $a$ ja $b$ 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