- 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