CSES - Etsintäkuulutus
  • Time limit: 1.00 s
  • Memory limit: 128 MB

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

Asiassa on kuitenkin yksi ongelma: Kaaleppi on etsintäkuulutettu kaupungissa cc. Tehtäväsi onkin selvittää, onko olemassa reittiä kaupungista aa kaupunkiin bb kulkematta kaupungin cc 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 nn, mm ja qq: kaupunkien määrä, teiden määrä ja kyselyiden määrä. Kaupungit on numeroitu 1,2,,n1,2,\ldots,n.

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

Lopuksi syötteessä on qq riviä, joista kullakin on kolme kokonaislukua aa, bb ja cc: pääseekö kaupungista aa kaupunkiin bb kulkematta kaupungin cc 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

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1q1051 \le q \le 10^5
  • 1a,b,cn1 \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