- Time limit: 1.00 s
- Memory limit: 512 MB
Pelaat peliä, jossa on n huonetta ja m teleporttia. Joka päivän alussa aloitat huoneesta 1 ja sinun tulee päästä huoneeseen n.
Voit käyttää jokaista teleporttia enintään kerran pelin aikana. Montako päivää voit pelata enintään, jos valitset reitit optimaalisesti?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: huoneiden ja teleporttien määrä. Huoneet on numeroitu 1,2,\dots,n.
Tämän jälkeen syötteessä on m riviä, jotka kuvaavat teleportit. Jokaisella rivillä on kaksi kokonaislukua a ja b: huoneesta a on teleportti huoneeseen b.
Pelissä ei ole kahta teleporttia, joiden alku- ja loppuhuone on sama.
Tuloste
Tulosta ensin kokonaisluku k: suurin päivien määrä. Tulosta sen jälkeen k reitin kuvaus, jossa on ensin huoneiden määrä reitillä ja sen jälkeen huoneet. Voit tulostaa minkä tahansa kelvollisen ratkaisun.
Rajat
- 2 \le n \le 500
- 1 \le m \le 1000
- 1 \le a,b \le n
Esimerkki
Syöte:
6 7 1 2 1 3 2 6 3 4 3 5 4 6 5 6
Tuloste:
2 3 1 2 6 4 1 3 4 6