CSES - Postinjako
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Tehtäväsi on jakaa posti kaikille kaupungin asukkaille. Tämän vuoksi haluat löytää reitin, jonka alku- ja loppupiste on postitoimisto ja joka kulkee tarkalleen kerran jokaista kaupungin katua pitkin.

Syöte

Syötteessä on ensin kaksi kokonaislukua nn ja mm: risteyksien määrä ja katujen määrä. Risteykset on numeroitu 1,2,,n1,2,\ldots,n. Postitoimisto sijaitsee risteyksessä 1.

Sitten syötteessä on mm riviä, jotka kuvaavat kadut. Jokaisella rivillä on kaksi kokonaislukua aa ja bb. Tämä tarkoittaa, että risteysten aa ja bb välillä on katu. Kaikki kadut ovat kaksisuuntaisia.

Mikään katu ei johda risteyksestä itseensä, ja kahden risteyksen välillä on enintään yksi katu.

Tuloste

Tulosta "10-4", jos reitti on olemassa, ja muuten "QAQ".

Jos reitti on olemassa, tulosta vielä kaikki reitin varrella olevat risteykset järjestyksessä. Voit tulostaa minkä tahansa kelvollisen reitin.

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

6 8
1 2
1 3
2 3
2 4
2 6
3 5
3 6
4 5

Tuloste:

10-4
1 2 6 3 2 4 5 3 1