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

• $1 \le n \le 10^5$
  
• $1 \le m \le 2 \cdot 10^5$
  
• $1 \le a,b \le n$
  

Esimerkki

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

Tuloste:
QAQ
4 2