OpenKattis
CS3233 Midterm Team Contest

Start

2019-04-01 09:00 UTC

CS3233 Midterm Team Contest

End

2019-04-01 13:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -232 days 13:39:31

Time elapsed

4:30:00

Time remaining

0:00:00

Problem A
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.

\includegraphics[width=0.8\textwidth ]{royal.png}
Figure 1: Illustration of the $1^\text {st}$ query of Sample Input 1. There are two direct routes Celestia can take from city $5$ to city $7$: ($5\to 2\to 7$) and ($5\to 2\to 9\to 7$). No matter which direct route Celestia takes, Luna can take the route ($1\to 8\to 4\to 6\to 10$).

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

Input

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

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