Pelaat peliä, jossa on $n$ planeettaa ja $m$ niiden välistä teleporttia. Kaikki teleportit ovat kaksisuuntaisia ja yhdistävät kaksi eri planeettaa.

Aloitat pelin tietyltä planeetalta, ja liikut joka vuorolla teleporttia pitkin jollekin toiselle planeetalle. Voit olettaa, että kaikki planeetat ovat yhteydessä toisiinsa teleporteilla.

Tehtäväsi on käsitellä $q$ kyselyä muotoa: "onko mahdollista aloittaa peli planeetalta $a$ ja päätyä $x$ vuoron jälkeen planeetalle $b$?"

Syöte

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

Tämän jälkeen syötteessä on $m$ riviä, jotka kuvaavat teleportit. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: planeettojen $a$ ja $b$ välillä on teleportti.

Lopuksi syötteessä on $q$ riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $x$.

Tuloste

Tulosta jokaisen kyselyn vastaus (YES tai NO) omalle rivilleen.

Esimerkki

Syöte:

4 5 6
1 2
2 3
1 3
2 4
3 4
1 2 2
1 4 1
1 4 5
2 2 0
2 2 1
3 4 8

Tuloste:

YES
NO
YES
YES
NO
YES

Selitys:

• Kyselyssä 1 mahdollinen reitti on $1 \rightarrow 3 \rightarrow 2$.
• Kyselyssä 3 mahdollinen reitti on $1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$.
• Kyselyssä 6 mahdollinen reitti on $3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$.

Osatehtävä 1 (42 pistettä)

• $2 \le n \le 50$
• $1 \le m \le 100$
• $1 \le q \le 100$
• $0 \le x \le 100$

Osatehtävä 2 (58 pistettä)

• $2 \le n \le 2500$
• $1 \le m \le 5000$
• $1 \le q \le 10^5$
• $0 \le x \le 10^9$