题目描述
Problem Description
IOI Railway operates on a single straight rail track with $N$ stations numbered from $1$ to $N$. Each station $i$ is directly connected to station $i + 1$ by a rail segment.
IOI Railway operates $M$ routes numbered from $1$ to $M$. Route $j$ starts at station $A_j$ and ends at station $B_j$. Trains on route $j$ stop at every station between $A_j$ and $B_j$. If $A_j < B_j$, the train stops at stations $A_j, A_j + 1, \ldots, B_j$. If $A_j > B_j$, the train stops at stations $A_j, A_j - 1, \ldots, B_j$.
JOI is a traveler with $Q$ travel plans. In the $k$-th plan, he intends to travel from station $S_k$ to station $T_k$ by train.
JOI is exhausted from long journeys and wants to ensure he has a seat on every train he takes. Therefore, he will only board a train at a station that is the starting station or within $K - 1$ stations from the starting station of that route. Specifically, for route $j$, if $A_j < B_j$, he will only board at stations $A_j, A_j + 1, \ldots, \min \{ A_j + K - 1, B_j - 1 \}$. If $A_j > B_j$, he will only board 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.
Given the details of IOI Railway's routes and JOI's travel plans, write a program to calculate the minimum number of train rides required for each of JOI's plans.
Input Format
The first line contains two positive integers $N$ and $K$.
The second line contains a positive integer $M$.
The next $M$ lines contain two positive integers each, $A_j$ and $B_j$.
The next line contains a positive integer $Q$.
The next $Q$ lines contain two positive integers each, $S_k$ and $T_k$.
Output Format
Output $Q$ lines. The $k$-th line should contain a single number representing the minimum number of train rides required for JOI's $k$-th plan. If it is impossible to complete the $k$-th plan, output -1.
Sample Input and Output
Input Sample #1
5 2
2
5 1
3 5
3
5 3
3 2
2 1
Output Sample #1
1
2
-1
Input Sample #2
6 3
2
1 6
5 1
4
5 1
6 3
3 6
2 1
Output Sample #2
1
-1
1
2
Input Sample #3
6 5
4
3 1
2 4
5 3
4 6
5
1 5
3 2
2 6
6 3
5 4
Output Sample #3
-1
1
2
-1
1
Input Sample #4
12 1
5
1 7
10 12
3 5
8 10
5 9
7
2 11
5 8
3 12
4 6
1 9
9 10
1 4
Output Sample #4
-1
1
4
-1
2
-1
1
Notes/Hints
[Sample Explanation #1]
For the first plan, JOI travels from station $5$ to station $3$. He boards the train on route $1$ at station $5$ and disembarks at station $3$. He makes one train ride. Output $1$.
For the second plan, JOI travels from station $3$ to station $2$. He boards the train on route $2$ at station $3$, disembarks at station $4$, then boards the train on route $1$ at station $4$ and disembarks at station $2$. He makes two train rides. Output $2$.
For the third plan, JOI travels from station $2$ to station $1$. It is impossible to complete this plan. Output -1.
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$.
[Data Range]
This problem is bundled test cases.
For $100\%$ of the data, $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 additional constraints.
Translated from JOI 2022 Final T4 "鉄道旅行 2 / Railway Trip 2"
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分