A Royal Problem

The two rulers of Equestria, Princess Celestia and Princess Luna, got into a massive argument, and Starlight Glimmer needs to help them resolve it, lest the kingdom of Equestria fall into chaos!

For now, Starlight needs to ensure that Celestia and Luna do not encounter each other while they cool off, or she risks reigniting the feud. This is problematic, because both princesses have very busy schedules and need to travel around Equestria often. Hence, she needs to decide wisely to make sure they do not see each other for the next $D$ days.

There are $N$ cities in Equestria, and $M$ roads connecting these cities. No road connects a city to itself, and there is at most one road between any two cities. It is possible to travel between any two different cities by taking one or more roads.

For simplicity, we label the cities $1, 2, \dots , N$; then, the $i^\text {th}$ road connects cities $A_ i$ and $B_ i$.

In the $i^\text {th}$
day, Celestia will travel from city $P_ i$ to city $Q_ i$. As Celestia’s daily schedule
is extremely hectic and unpredictable, Starlight neither knows
the route the princess will take, nor can she decide it. She
also does not know what time the princess will leave nor what
time she will arrive. She only knows that Celestia will take a
*direct* route from $P_ i$ to $Q_ i$. A direct route is a route that
neither visits the same city nor takes the same road more than
once. Note that a direct route is not necessarily a shortest
route.

What Starlight can decide, however, is Luna’s route. On the
$i^\text {th}$ day, Luna
needs to travel from city $R_
i$ to city $S_ i$.
Starlight must decide Luna’s route in such a way that *no matter* which direct route Celestia takes, and
no matter what time Celestia leaves or arrives, she can
guarantee that Luna will not meet Celestia. That is, if Luna
takes this route, no matter which route Celestia takes, it must
be impossible for Celestia and Luna to be at the same city or
the same road at the same time. Note that Luna’s route need not
be a direct route.

Can you help Starlight decide whether it is possible to arrange these routes?

The first line of input contains three integers, $N$ ($2 \leq N \leq 200\, 000$), $M$ ($N-1 \leq M \leq 400\, 000$) and $D$ ($1 \leq D \leq 200\, 000$), the number of cities, the number of roads, and the number of days Starlight needs to ensure that the two princesses will not meet, respectively.

The next $M$ lines contain the descriptions of the roads. In particular, the $i^\text {th}$ of these lines contains two integers $A_ i$ and $B_ i$ ($1\leq A_ i, B_ i \leq N$; $A_ i \neq B_ i$), denoting that the $i^\text {th}$ road connects cities $A_ i$ and $B_ i$.

The next $D$ lines contain the descriptions of the agendas of each day. In particular, the $i^\text {th}$ of these lines contains four integers $P_ i$, $Q_ i$, $R_ i$ and $S_ i$ ($1 \leq P_ i, Q_ i, R_ i, S_ i \leq N$; $P_ i \neq Q_ i$; $R_ i \neq S_ i$), denoting that on the $i^\text {th}$ day, Celestia will travel from city $P_ i$ to city $Q_ i$, and Luna needs to travel from city $R_ i$ to city $S_ i$.

It is guaranteed that there is at most one road between any two cities, and that it is possible to travel between any two different cities by taking one or more roads.

Output $D$ lines. The
$i^\text {th}$ of these
lines should contain `YES` or
`NO`, whether or not it is possible for
Starlight to arrange a route for the $i^\text {th}$ day that ensures Luna
will not meet Celestia.

Sample Input 1 | Sample Output 1 |
---|---|

10 12 4 1 2 1 8 2 4 2 5 2 7 2 8 2 9 3 6 4 6 4 8 6 10 7 9 5 7 1 10 9 4 3 10 5 6 1 8 1 10 5 7 |
YES YES NO NO |

Sample Input 2 | Sample Output 2 |
---|---|

3 2 4 1 2 2 3 2 3 2 1 3 2 2 1 2 3 1 2 3 2 1 2 |
NO NO NO NO |