Code Submission Evaluation System Login

Datatähti-valmennus

Katuverkko


Task | Statistics


CSES - Katuverkko

Time limit:1.00 s Memory limit:128 MB

Kaupungissa on $n$ risteystä ja niiden välillä on $m$ 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 $n$ ja $m$: risteysten määrä ja katujen määrä. Risteykset on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, jotka kuvaavat kadut. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$. Tämä tarkoittaa, että kaupungissa on katu risteyksestä $a$ risteykseen $b$. Kaikki kadut ovat yksisuuntaisia.

Tuloste

Tulosta "10-4", jos kaikki reitit ovat olemassa, ja muuten "QAQ".

Jos vastaus on "QAQ", tulosta vielä esimerkki risteyksistä $a$ ja $b$, joille pätee, että $a$:sta ei pääse $b$:hen.

Rajat
Esimerkki

Syöte:
4 5
1 2
2 3
3 1
1 4
3 4


Tuloste:
QAQ
4 2