- Time limit: 1.00 s
- Memory limit: 128 MB
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$
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