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

Syrjälän tietoverkossa on nn tietokonetta, joiden välillä on mm yhteyttä. Tehtäväsi on selvittää, voiko Uolevi lähettää viestin Maijalle, ja jos voi, mikä on pienin määrä koneita, joiden kautta viesti voi kulkea.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja mm: koneiden määrä ja yhteyksien määrä. Koneet on numeroitu 1,2,,n1,2,\ldots,n. Uolevin koneen numero on 1, ja Maijan koneen numero on nn.

Sitten syötteessä on mm riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: koneiden aa ja bb välillä on yhteys.

Koneesta ei ole koskaan yhteyttä itseensä, ja kahden koneen välillä on enintään yksi yhteys.

Tuloste

Jos Uolevi voi lähettää viestin Maijalle, tulosta "10-4", ja muuten "QAQ".

Jos lähetys onnistuu, tulosta sitten kokonaisluku kk: pienin määrä koneita, joiden kautta viesti voi kulkea. Tämän jälkeen tulosta esimerkki kk koneen reitistä Uolevin koneelta Maijan koneelle. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

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

Tuloste:

10-4
3
1 4 5