J. Let's talk of graves, of worms, and epitaphs
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To write a truly thrilling story, one needs to have a set of literary themes. Shakespeare is well-versed in using literary devices in his stories to establish thematic connections between the various subplots of his plays.

We represent one of Shakespeare's works as a graph, where the nodes represent literary themes (love, greed, nihilistic optimism, etc.), and edges represent literary devices. When Shakespeare uses a literary device, he draws a (directed) edge from theme $$$u$$$ to theme $$$v$$$.

Shakespeare is worried that his use of literary devices is getting repetitive. Specifically, a literary device between themes $$$u$$$ and $$$v$$$ is repetitive iff it creates a thematic loop between $$$u$$$ and $$$v$$$ (that is to say, it creates a cycle in the graph containing themes $$$u$$$ and $$$v$$$).

Shakespeare has an existing play and some literary devices that he wishes to add to the play, in the form of a list of queries. Each query consists of two nodes $$$u$$$, $$$v$$$ denoting a literary device connecting theme $$$u$$$ to theme $$$v$$$. If this literary device creates a thematic loop between $$$u$$$ and $$$v$$$, output "YES". Otherwise, output "NO". Then, add the literary device to the graph.

Note that Shakespeare only cares about the current two themes $$$u$$$ and $$$v$$$ when considering a query. That is, he does not care about cycles that don't contain $$$u$$$ and $$$v$$$, and you shouldn't consider them when answering.

If you succeed in your task, you will forever be cemented as one of the greatest literary artists of all time!

Input

The first line contains three integers $$$N, M, Q$$$, representing the number of nodes (themes), the number of edges (initial literary devices), and the number of queries (additional literary devices), respectively. ($$$1 \le N \le 1000, 0 \le M \le 5 \cdot 10^5, 1 \le Q \le 1000$$$)

The next $$$M$$$ lines each consist of two integers $$$u_i, v_i$$$ denoting a directed edge from theme $$$u_i$$$ to theme $$$v_i$$$ in the initial play. It is guaranteed that no thematic loops will exist in the initial play. ($$$1 \le u_i, v_i \le N, u_i \neq v_i$$$)

The final $$$Q$$$ lines each consist of two integers $$$x_j, y_j$$$ denoting the addition of a directed edge from theme $$$x_j$$$ to theme $$$y_j$$$. ($$$1 \le x_j, y_j \le N, x_j \neq y_j$$$)

Output

For each query, output "YES" if the query results in a thematic loop between the two given themes; otherwise, output "NO".

Examples
Input
9 9 6
1 8
1 2
2 4
2 3
3 4
3 7
5 6
5 9
6 9
8 4
7 6
5 3
9 7
9 1
1 9
Output
NO
NO
NO
YES
YES
YES
Input
5 4 3
1 2
2 3
3 4
4 5
1 3
5 2
3 5
Output
NO
YES
YES
Note

For the first sample test case, here is the initial graph:

And here is the final graph.