Description

Xiao G and Xiao H are playing a treasure-hunting game. There are $n$ rooms in a line, numbered $1,2,\cdots,n$, with a door between each pair of adjacent rooms. Some doors are locked (so they require the corresponding keys to open), and the remaining doors can be opened directly. Xiao G tells Xiao H which room contains the key for each lock (each lock has exactly one corresponding key), and then gives $p$ instructions: for the $i$-th one, Xiao H is asked to go from room $S_i$ to room $T_i$. However, Xiao G may intentionally include dead ends in the instructions, and Xiao H does not want to waste extra energy trying, so he wants to determine in advance whether a path exists for each instruction.

Can you answer for Xiao H?

Input Format

The first line contains three integers $n, m, p$, representing that there are $n$ rooms, $m$ locked doors, and $p$ queries. The next $m$ lines each contain two integers $x, y$, meaning that the key for the lock between rooms $x$ and $x+1$ is located in room $y$. The next $p$ lines follow, where the $i$-th line contains two integers $S_i, T_i$, representing one query.

Output Format

Output $p$ lines, each containing YES or NO, indicating whether it is reachable.

5 4 5 
1 3
2 2 
3 1
4 4
2 5
3 5
4 5 
2 1
3 1

YES
NO
YES
YES
NO

7 5 4
2 2
3 3 
4 2 
5 3 
6 6
2 1
3 4
3 7
4 5

YES
YES
NO
NO

Hint

Constraints

$1 \le n, p \le 10^6$, $0 \le m < n$, $1 \le x, y, S_i, T_i < n$. It is guaranteed that $x$ is not repeated.

Translated by ChatGPT 5