- Time limit: 1.00 s
- Memory limit: 128 MB
Kaupunki muodostuu risteyksestä ja tiestä. Kaupunkiin halutaan perustaa bussilinja, joka kulkee katuja pitkin ja ohittaa joukon risteyksiä. Linjan tulee alkaa samasta risteyksestä kuin mihin se päättyy ja siinä tulee olla vähintään kolme risteystä.
Tehtäväsi on selvittää, voiko linjaa muodostaa, ja jos voi, antaa esimerkki, miten linjan voi muodostaa.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : risteyksien määrä ja katujen määrä. Risteykset on numeroitu .
Sitten syötteessä on riviä, jotka kuvaavat kadut. Jokaisella rivillä on kaksi kokonaislukua ja : katu lähtee risteyksestä ja päättyy risteykseen . Jokainen katu on yksisuuntainen, ja se alkaa ja päättyy eri risteyksessä.
Tuloste
Tulosta ensin "10-4", jos linjan voi muodostaa, ja muuten "QAQ".
Jos linjan voi muodostaa, tulosta sitten kokonaisluku : risteyksien määrä reitillä. Tulosta lopuksi järjestyksessä jokainen reitillä oleva risteys. Voit tulostaa minkä tahansa kelvollisen ratkaisun.
Rajat
Esimerkki
Syöte:
4 5 1 3 2 1 2 4 3 2 3 4
Tuloste:
10-4 4 2 1 3 2