CSES - 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 $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.

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