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

Bittimaassa on nn kaupunkia, joiden välillä on mm tietä. Tehtäväsi on suunnitella kiertomatka, joka alkaa jostain kaupungista, käy joissakin muissa kaupungeissa ja palaa takaisin lähtökaupunkiin. Sinun tulee kulkea teitä pitkin ja saat käydä kussakin muussa kaupungissa vain kerran.

Syöte

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

Sitten syötteessä on mm riviä, joista jokainen kuvaa yhden tien. Rivillä on kaksi kokonaislukua aa ja bb: minkä kaupunkien välillä tie on.

Tie yhdistää aina kaksi eri kaupunkia, ja kahden kaupungin välillä on enintään yksi tie.

Tuloste

Tulosta "10-4", jos kiertomatka on mahdollinen, ja muuten "QAQ". Kiertomatkaan täytyy kuulua vähintään kolme kaupunkia.

Jos kiertomatka onnistuu, tulosta sitten kokonaisluku kk: kaupunkien määrä. Tämän jälkeen tulosta kk kaupunkia, jotka kuvaavat kiertomatkan. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

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:

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

Tuloste:

10-4
4
3 5 1 3