AT_joi2022ho_d.鉄道旅行 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】

对于第一个计划，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 T4「鉄道旅行 2 / Railway Trip 2」