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