CSES - Reitit
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Pelaat peliä, jossa on nn huonetta ja mm teleporttia. Joka päivän alussa aloitat huoneesta 11 ja sinun tulee päästä huoneeseen nn.

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 nn ja mm: huoneiden ja teleporttien määrä. Huoneet on numeroitu 1,2,,n1,2,\dots,n.

Tämän jälkeen syötteessä on mm riviä, jotka kuvaavat teleportit. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: huoneesta aa on teleportti huoneeseen bb.

Pelissä ei ole kahta teleporttia, joiden alku- ja loppuhuone on sama.

Tuloste

Tulosta ensin kokonaisluku kk: suurin päivien määrä. Tulosta sen jälkeen kk reitin kuvaus, jossa on ensin huoneiden määrä reitillä ja sen jälkeen huoneet. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

  • 2n5002 \le n \le 500
  • 1m10001 \le m \le 1000
  • 1a,bn1 \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