Annettuna on suunnattu verkko, jossa voi olla syklejä. Tehtäväsi on vastata joukkoon kyselyitä muotoa "pääseekö solmusta a solmuun b".

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut n, m ja q: solmujen määrä, kaarten määrä ja kyselyjen määrä. Solmut on numeroitu kokonaisluvuin 1,2,\ldots,n.

Sitten syötteessä on m riviä, joista jokainen kuvaa yhden kaaren. Kullakin rivillä on kaksi kokonaislukua a ja b: solmusta a on kaari solmuun b.

Lopuksi syötteessä on q riviä, joista jokainen kuvaa yhden kyselyn. Kullakin rivillä on kaksi kokonaislukua a ja b: pääseekö solmusta a solmuun b?

Tuloste

Tulosta jokaiseen kyselyyn "10-4", jos solmusta a pääsee solmuun b, ja muuten "QAQ".

Rajat

• 1 \le n \le 5 \cdot 10^4
• 1 \le m \le 10^5
• 1 \le q \le 10^5

Esimerkki

Syöte:

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

Tuloste:

10-4
QAQ
10-4