P4436 [HNOI/AHOI2018] Game

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?

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 $p$ lines, each containing `YES` or `NO`, indicating whether it is reachable.

 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