- Time limit: 1.00 s
- Memory limit: 128 MB
Kaupungissa on risteystä ja niiden välillä on katua. Tehtäväsi on tarkistaa, onko katuverkko suunniteltu niin, että mistä tahansa risteyksestä pääsee mihin tahansa toiseen risteykseen katuja pitkin.
Syöte
Syötteen alussa on kaksi kokonaislukua ja : risteysten määrä ja katujen määrä. Risteykset on numeroitu .
Sitten syötteessä on riviä, jotka kuvaavat kadut. Jokaisella rivillä on kaksi kokonaislukua ja . Tämä tarkoittaa, että kaupungissa on katu risteyksestä risteykseen . Kaikki kadut ovat yksisuuntaisia.
Tuloste
Tulosta "10-4", jos kaikki reitit ovat olemassa, ja muuten "QAQ".
Jos vastaus on "QAQ", tulosta vielä esimerkki risteyksistä ja , joille pätee, että :sta ei pääse :hen.
Rajat
Esimerkki
Syöte:
4 5 1 2 2 3 3 1 1 4 3 4
Tuloste:
QAQ 4 2