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