- Time limit: 1.00 s
- Memory limit: 128 MB
Syrjälän tietoverkossa on tietokonetta, joiden välillä on 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 ja : koneiden määrä ja yhteyksien määrä. Koneet on numeroitu . Uolevin koneen numero on 1, ja Maijan koneen numero on .
Sitten syötteessä on riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua ja : koneiden ja 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 : pienin määrä koneita, joiden kautta viesti voi kulkea. Tämän jälkeen tulosta esimerkki koneen reitistä Uolevin koneelta Maijan koneelle. Voit tulostaa minkä tahansa kelvollisen ratkaisun.
Rajat
Esimerkki
Syöte:
5 5 1 2 1 3 1 4 2 3 5 4
Tuloste:
10-4 3 1 4 5