CSES - Katuverkko
  • Time limit: 1.00 s
  • Memory limit: 128 MB

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

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

Tuloste

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

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

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

4 5
1 2
2 3
3 1
1 4
3 4

Tuloste:

QAQ
4 2