Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Kielletty kaupunki


Task | Statistics


CSES - Kielletty kaupunkiCSES - Kielletty kaupunki

Time limit:1.00 s Memory limit:512 MB

Bittimaassa on $n$ kaupunkia, joiden välillä on $m$ tietä. Minkä tahansa kahden kaupungin välillä on jokin reitti.

Bittimaan johtaja haluaa tehdä yhdestä kaupungista kielletyn kaupungin, johon maan asukkaat eivät saa astua. Tehtäväsi on selvittää tavat valita kielletty kaupunki niin, että kaikkien muiden kaupunkien välillä on edelleen reitti.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: kaupunkien ja teiden määrä. Kaupungit on numeroitu $1,2,\dots,n$.

Sitten syötteessä on $n$ riviä, jotka kuvaavat tiet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: kaupunkien $a$ ja $b$ välillä on tie. Jokainen tie on kaksisuuntainen, yhdistää kaksi eri kaupunkia ja sama tie ei toistu monta kertaa.

Tuloste

Tulosta ensin kokonaisluku $k$: kaupunkien määrä

Tulosta sitten rivi, joka sisältää kaikki $k$ kaupunkia. Voit tulostaa kaupungit missä tahansa järjestyksessä.

Rajat
Esimerkki

Syöte:
4 4
1 2
1 3
2 3
2 4


Tuloste:
3
1 3 4