Kaaleppi on tällä hetkellä kaupungissa a ja haluaa siirtyä kaupunkiin b. Tiedossasi on kaikki seudun kaupungit ja niiden väliset tiet.

Asiassa on kuitenkin yksi ongelma: Kaaleppi on etsintäkuulutettu kaupungissa c. Tehtäväsi onkin selvittää, onko olemassa reittiä kaupungista a kaupunkiin b kulkematta kaupungin c kautta.

Lisähaasteena sinun pitää käsitellä suuri määrä tällaisia kyselyitä annetussa kaupunkiverkossa.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua n, m ja q: kaupunkien määrä, teiden määrä ja kyselyiden määrä. Kaupungit on numeroitu 1,2,\ldots,n.

Sitten syötteessä on m riviä, joista kullakin on kaksi kokonaislukua a ja b: kaupunkien a ja b välillä on tie. Kaikki tiet ovat kaksisuuntaisia, eikä mistään kaupungista ole tietä itseensä.

Lopuksi syötteessä on q riviä, joista kullakin on kolme kokonaislukua a, b ja c: pääseekö kaupungista a kaupunkiin b kulkematta kaupungin c kautta?

Voit olettaa, että minkä tahansa kahden kaupungin välillä on olemassa jokin reitti.

Tuloste

Tulosta jokaiseen kyselyyn "10-4", jos reitti on mahdollinen, ja muuten "QAQ".

Rajat

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

Esimerkki

Syöte:

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

Tuloste:

10-4
QAQ
10-4