Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Matkareitti I


Task | Statistics


CSES - Matkareitti ICSES - Matkareitti I

Time limit:1.00 s Memory limit:512 MB

Bittimaassa on $n$ kaupunkia, joiden välillä on $m$ tietä. Haluat matkustaa kaupungista $1$ kaupunkiin $n$.

Tehtäväsi on selvittää kaupungit, joiden kautta kuljet varmasti reitilläsi riippumatta siitä, kuinka valitset reitin.

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.

Voit olettaa, että kaupungista $1$ kaupunkiin $n$ on olemassa jokin reitti.

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 2 4