Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Etsintäkuulutus

Etsintäkuulutus


View task | Model solution | Statistics


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.

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
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