Etsintäkuulutus

• Time limit: 1.00 s
• Memory limit: 128 MB

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