题目描述

译自 JOI 2022 Final T4「鉄道旅行 2 / Railway Trip 2」

IOI 公司正在运营铁路，其共有 $N$ 个排成一行的从 $1$ 到 $n$ 编号的火车站，第 $1$ 站和第 $2$ 站相邻，第 $2$ 站和第 $3$ 站相邻，以此类推，相邻的火车站之间有铁路直接连接。

IOI 公司旗下共有 $M$ 条线路，从 $1$ 到 $M$ 编号，第 $i$ 条线路从第 $A_i$ 站出发抵达第 $B_i$ 站，并在中间的每一个站停留。

JOI 君制定了 $Q$ 个旅游计划，第 $i$ 个旅行计划是从 $S_i$ 站乘火车到 $T_i$ 站。

由于站在车上实在太累了，JOI 君决定，若他要在某站乘坐某一条线路 $j$，如果 $A_j<B_j$，JOI 君可以从第 $A_j,A_j+1,\ldots,\min\{A_j+K-1,B_j-1\}$ 站上车，如果 $A_j>B_j$，JOI 君可以从第 $A_j,A_j-1,\ldots,\max\{A_j-K+1,B_j+1\}$ 站上车。JOI 君可以在每一个中转站下车或终点站下车。

为了花费最少的钱，他决定乘坐最少的线路，请你帮助他计算最少的乘坐线路数。

输入格式

第一行两个整数 $N,K$。

第二行一个整数 $M$。

接下来 $M$ 行，一行两个整数 $A_i,B_i$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，一行两个整数 $S_i,T_i$。

输出格式

输出 $Q$ 行，一行一个整数，表示某一个计划的最少的乘坐线路数，如果计划无法实现，输出 $-1$。

5 2
2
5 1
3 5
3
5 3
3 2
2 1

1
2
-1

对于第一个计划，一种可能的方案是 $5\to 3$ 。

对于第二个计划，一种可能的方案是 $3\to 4\to 2$。

这个样例满足子任务 $1,2,6$ 的限制。

6 3
2
1 6
5 1
4
5 1
6 3
3 6
2 1

1
-1
1
2

这个样例满足子任务 $1,2,6$ 的限制。

6 5
4
3 1
2 4
5 3
4 6
5
1 5
3 2
2 6
6 3
5 4

-1
1
2
-1
1

这个样例满足子任务 $1,2,4,6$ 的限制。

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

-1
1
4
-1
2
-1
1

这个样例满足子任务 $1,2,5,6$ 的限制。

数据范围

对于全部数据，$2\le N\le 10^5$，$1\le K< N$，$1\le M\le 2\times 10^5$，$1\le A_i,B_i,S_i,T_i\le N$，$\forall i,A_i\not= B_i,S_i\not= T_i$，$\forall i,j,(A_i,B_i)\not=(A_j,B_j),(S_i,T_i)\not=(S_j,T_j)$，$1\le Q\le 5\times 10^4$。