Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Matkareitti II


Task | Statistics


CSES - Matkareitti IICSES - Matkareitti II

Time limit:1.00 s Memory limit:512 MB

Bittimaassa on $n$ kaupunkia, joiden välillä on $m$ tietä. Jokaisen kahden kaupungin välillä on jokin reitti.

Tehtäväsi on käsitellä $q$ kyselyä muotoa: voitko matkustaa kaupungista $a$ kaupunkiin $b$ kulkematta kaupungin $c$ kautta?

Syöte

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

Sitten syötteessä on $n$ riviä, jotka kuvaavat tiet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: kaupunkien $a$ ja $b$ välillä on tie. Jokainen tie on kaksisuuntainen, yhdistää kaksi eri kaupunkia ja sama tie ei toistu monta kertaa.

Lopuksi syötteessä on $q$ riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: haluat matkustaa kaupungista $a$ kaupunkiin $b$ kulkematta kaupungin $c$ kautta.

Tuloste

Tulosta jokaiseen kyselyyn vastauksena "YES", jos reitti on mahdollinen, ja "NO" muuten.

Rajat
Esimerkki

Syöte:
4 4 3
1 2
1 3
2 3
2 4
1 4 2
1 4 3
2 2 1


Tuloste:
NO
YES
YES