CSES - Matkareitti II
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Bittimaassa on nn kaupunkia, joiden välillä on mm tietä. Jokaisen kahden kaupungin välillä on jokin reitti.

Tehtäväsi on käsitellä qq kyselyä muotoa: voitko matkustaa kaupungista aa kaupunkiin bb kulkematta kaupungin cc kautta?

Syöte

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

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

Lopuksi syötteessä on qq riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kolme kokonaislukua aa, bb ja cc: haluat matkustaa kaupungista aa kaupunkiin bb kulkematta kaupungin cc kautta.

Tuloste

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

Rajat

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