CSES - 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 $m$ 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
  • $1 \le n, q \le 10^5$
  • $0 \le m \le 2 \cdot 10^5$
  • $1 \le a,b,c \le n$
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