- 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 m 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
- 1 \le n \le 2 \cdot 10^5
- 0 \le m \le 5 \cdot 10^5
- 1 \le a,b \le n
Esimerkki
Syöte:
4 4 1 2 1 3 2 3 2 4
Tuloste:
3 1 3 4