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

• 1 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le k \le m
• 1 \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