P8163 [JOI 2022 Final] Railway Trip 2 / Railway Trip 2

The IOI Railway Company operates routes on a single railway track. The track is a straight line, and there are $N$ stations on it, numbered $1 \sim N$. Station $i$ and station $i + 1$ are directly connected by a piece of track. The IOI Railway Company is operating $M$ routes, numbered $1 \sim M$. Route $j$ starts at $A_j$ and ends at $B_j$, and the train stops at every station. That is, if $A_j < B_j$, a train on route $j$ stops in order at stations $A_j, A_j + 1, \ldots, B_j$. If $A_j > B_j$, a train on route $j$ stops in order at stations $A_j, A_j - 1, \ldots, B_j$. JOI is a traveler. He has $Q$ travel plans. In the $k$-th travel plan, he plans to travel from station $S_k$ to station $T_k$ by taking trains. However, JOI is exhausted from long-distance travel. He wants every train he takes to have an empty seat so that he can rest. Therefore, JOI will only board within $K$ stations from the starting station of a route (including the starting station). In other words, for route $j$, if $A_j < B_j$, then he will only board a train on route $j$ at stations $A_j, A_j + 1, \ldots, \min \{ A_j + K - 1, B_j - 1 \}$. If $A_j > B_j$, then he will only board a train on route $j$ at stations $A_j, A_j - 1, \ldots, \max \{ A_j - K + 1, B_j + 1 \}$. Under these conditions, JOI wants to minimize the number of train rides as much as possible. Given the route information of the IOI Railway Company and JOI's plans, write a program to compute, for each of JOI's plans, the minimum number of rides he needs.

The first line contains two positive integers $N, K$. The second line contains one positive integer $M$. The next $M$ lines each contain two positive integers $A_j, B_j$ on the $j$-th line. The next line contains one positive integer $Q$. The next $Q$ lines each contain two positive integers $S_k, T_k$ on the $k$-th line.

Output $Q$ lines. The $k$-th line contains one number, representing the minimum number of rides needed for JOI to complete his $k$-th plan. If it is impossible to complete the $k$-th plan, output `-1`.

**[Sample Explanation #1]** For the first plan, JOI wants to travel from station $5$ to station $3$. Specifically, this plan can be carried out as follows: JOI boards route $1$ at station $5$ and gets off at station $3$. In total, JOI takes one train. Since it is impossible to complete this plan with fewer than $1$ ride, output $1$ on the first line. For the second plan, JOI wants to travel from station $3$ to station $2$. Specifically, this plan can be carried out as follows: JOI boards route $2$ at station $3$ and gets off at station $4$; then he boards route $1$ at station $4$ and gets off at station $2$. In total, JOI takes two trains. Since it is impossible to complete this plan with fewer than $2$ rides, output $2$ on the second line. For the third plan, JOI wants to travel from station $2$ to station $1$. Since it is impossible to complete this plan, output `-1` on the third line. This sample satisfies the constraints of subtasks $1, 2, 6$. **[Sample Explanation #2]** This sample satisfies the constraints of subtasks $1, 2, 6$. **[Sample Explanation #3]** This sample satisfies the constraints of subtasks $1, 2, 4, 6$. **[Sample Explanation #4]** This sample satisfies the constraints of subtasks $1, 2, 5, 6$. ---- **[Constraints]** **This problem uses bundled testdata.** For $100\%$ of the testdata, $2 \le N \le {10}^5$, $1 \le K \le N - 1$, $1 \le M \le 2 \times {10}^5$, $1 \le Q \le 5 \times {10}^4$, $1 \le A_j, B_j, S_k, T_k \le N$, $A_j \ne B_j$, $S_k \ne T_k$, $(A_j, B_j) \ne (A_k, B_k)$ ($j \ne k$), $(S_k, T_k) \ne (S_l, T_l)$ ($k \ne l$). - Subtask $1$ ($8$ points): $N, M, Q \le 300$. - Subtask $2$ ($8$ points): $N, M, Q \le 2000$. - Subtask $3$ ($11$ points): $Q = 1$. - Subtask $4$ ($25$ points): $K = N - 1$. - Subtask $5$ ($35$ points): $A_j < B_j$, $S_k < T_k$. - Subtask $6$ ($13$ points): No special constraints. ---- **Translated from [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T4 "[鉄道旅行 2 ](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t4.pdf) / [Railway Trip 2](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t4-en.pdf)".** Translated by ChatGPT 5