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

Pelaat peliä, jossa on nn tasoa sekä mm teleporttia, joiden avulla voit liikkua tasolta toiselle. Voitat pelin, jos pääset tasolta 1 tasolle nn niin että käytät tasan kerran jokaista teleporttia.

Tehtäväsi on selvittää, pystytkö voittamaan pelin, ja jos pystyt, mikä on yksi mahdollinen tapa kulkea teleporteissa.

Syöte

Syötteessä on ensin kaksi kokonaislukua nn ja mm: tasojen määrä ja teleporttien määrä. Tasot on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, jotka kuvaavat teleportit. Jokaisella rivillä on kaksi kokonaislukua aa ja bb. Tämä tarkoittaa, että tasolta aa pääsee teleportilla tasolle bb. Kaikki teleportit ovat yksisuuntaisia.

Tuloste

Tulosta ensin "10-4", jos voit voittaa pelin, ja muuten "QAQ".

Jos voit voittaa pelin, tulosta vielä m+1m+1 kokonaislukua, jotka kuvaavat, missä järjestyksessä siirryt tasolta toiselle.

Rajat

  • 2n1052 \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 2
1 3
2 4
2 5
3 1
4 2

Tuloste:

10-4
1 3 1 2 4 2 5