[JOI 2022 Final] 铁路旅行 2 (Railway Trip 2)
题目描述
IOI 铁路公司在一条铁轨上运营线路。铁轨为一条直线,该铁轨上有 $N$ 个车站,编号为 $1 \sim N$。车站 $i$ 与车站 $i + 1$ 之间由一条铁轨直接连接。
IOI 铁路公司正在运营 $M$ 条线路,编号为 $1 \sim M$。线路 $j$ 的起点为 $A_j$,终点为 $B_j$,列车在每一站均会停靠,即如果 $A_j < B_j$,一列 $j$ 号线的列车会按顺序在车站 $A_j, A_j + 1, \ldots, B_j$ 停靠。如果 $A_j > B_j$,一列 $j$ 号线的列车会按顺序在车站 $A_j, A_j - 1, \ldots, B_j$ 停靠。
JOI 君是一个旅行者。他有 $Q$ 个旅行计划。在第 $k$ 个旅行计划中他计划从车站 $S_k$ 通过乘坐列车前往车站 $T_k$。
然而,JOI 君因长途跋涉而疲惫不堪。他希望他乘坐的列车均有空座以便休息。因此 JOI 君决定,只有当某条线路的起点站是第 $K$ 个或更早的车站时,他才会在该站乘坐该条线路的列车。换句话说,对于线路 $j$,如果 $A_j < B_j$,那么他只会在车站 $A_j, A_j + 1, \ldots, \min \{ A_j + K - 1, B_j - 1 \}$ 乘上线路 $j$ 的列车。如果 $A_j > B_j$,那么他只会在车站 $A_j, A_j - 1, \ldots, \max \{ A_j - K + 1, B_j + 1 \}$ 乘上线路 $j$ 的列车。
在这些条件下,JOI 君希望尽量减少乘坐火车的次数。
给出 IOI 铁路公司的线路信息和 JOI 君的计划,写一个程序计算对于 JOI 君的每一个计划,他所需的最小乘车次数。
输入输出格式
输入格式
第一行,两个正整数 $N, K$。
第二行,一个正整数 $M$。
接下来 $M$ 行,第 $j$ 行两个正整数 $A_j, B_j$。
接下来一行,一个正整数 $Q$。
接下来 $Q$ 行,第 $k$ 行两个正整数 $S_k, T_k$。
输出格式
输出 $Q$ 行,第 $k$ 行一个数,表示对于 JOI 君的第 $k$ 个计划,他实现该计划所需的最小乘车次数。如果无论如何无法实现第 $k$ 个计划,则输出 `-1`。
输入输出样例
输入样例 #1
5 2
2
5 1
3 5
3
5 3
3 2
2 1
输出样例 #1
1
2
-1
输入样例 #2
6 3
2
1 6
5 1
4
5 1
6 3
3 6
2 1
输出样例 #2
1
-1
1
2
输入样例 #3
6 5
4
3 1
2 4
5 3
4 6
5
1 5
3 2
2 6
6 3
5 4
输出样例 #3
-1
1
2
-1
1
输入样例 #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
输出样例 #4
-1
1
4
-1
2
-1
1
说明
**【样例解释 \#1】**
对于第一个计划,JOI 君要从车站 $5$ 前往车站 $3$。具体地,此计划可以通过如下方式实现:JOI 君在车站 $5$ 乘上 $1$ 号线的列车,并在车站 $3$ 下车。JOI 君总共乘坐了一次列车。由于不可能花费比 $1$ 更少的乘车次数实现该计划,在第一行输出 $1$。
对于第二个计划,JOI 君要从车站 $3$ 前往车站 $2$。具体地,此计划可以通过如下方式实现:JOI 君在车站 $3$ 乘上 $2$ 号线的列车,并在车站 $4$ 下车;然后在车站 $4$ 乘上 $1$ 号线的列车,并在车站 $2$ 下车。JOI 君总共乘坐了两次列车。由于不可能花费比 $2$ 更少的乘车次数实现该计划,在第二行输出 $2$。
对于第一个计划,JOI 君要从车站 $2$ 前往车站 $1$。由于无论如何无法实现该计划,在第三行输出 `-1`。
这个样例满足子任务 $1, 2, 6$ 的限制。
**【样例解释 \#2】**
这个样例满足子任务 $1, 2, 6$ 的限制。
**【样例解释 \#3】**
这个样例满足子任务 $1, 2, 4, 6$ 的限制。
**【样例解释 \#4】**
这个样例满足子任务 $1, 2, 5, 6$ 的限制。
----
**【数据范围】**
**本题采用捆绑测试。**
对于 $100 \%$ 的数据,$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$)。
- 子任务 $1$($8$ 分):$N, M, Q \le 300$。
- 子任务 $2$($8$ 分):$N, M, Q \le 2000$。
- 子任务 $3$($11$ 分):$Q = 1$。
- 子任务 $4$($25$ 分):$K = N - 1$。
- 子任务 $5$($35$ 分):$A_j < B_j$,$S_k < T_k$。
- 子任务 $6$($13$ 分):无特殊限制。
----
**译自 [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)」**