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