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

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

Sitten syötteessä on mm riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: koneiden aa ja bb 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 kk riviä, jotka kuvaavat katkeamiset. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: koneiden aa ja bb välinen yhteys katkeaa.

Tuloste

Tulosta jokaisen katkeamisen jälkeen aliverkkojen määrä.

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1km1 \le k \le m
  • 1a,bn1 \le a,b \le n

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