配点: 100 点
IOI 铁路是 1 经营一条铁路线。排列在IOI铁道线上 有 N 站, 它们的编号最大为1 它们的编号最大为 N 。每个 i (1 \leqq i \leqq N - 1),车站 i 和车站 i + 1 由铁轨连接。
IOI铁路线有 M 有一个操作系统, 它们的编号最大为1 它们的编号最大为 M 。血统 j (1 \leqq j \leqq M) 列车的始发站是 车站 A_j ,终点站为车站 B_j 。火车在每个车站停靠。换句话说,系统 j 火车是A_j < B_j 能登站 按 A_j,駅 A_j + 1,\dots,駅 B_j 的顺序停止, 按照A_j > B_j 能登站 按 A_j,駅 A_j - 1,\dots,駅 B_j 的顺序停止。
旅行者JOI君是 我正在考虑Q 旅行计划。k 番目 (1 \leqq k \leqq Q)的计划是 车站 S_k 出发 您将通过转乘多趟列车到达 T_k 。
然而,JOI君因为长途旅行而感到疲惫,所以他想登上空车并坐下来。因此,JOI君将从列车的始发站(包括始发站)登上某趟列车。K 仅来自站内站。也就是说,JOI君是一个血统。 当您登上 j 火车时,A_j < B_j 奈良站 A_j,駅 A_j + 1,\dots,駅 \min\{A_j + K - 1, B_j - 1\} 出发, 您可以从A_j > B_j 奈良站 A_j,駅 A_j - 1,\dots,駅 \max\{A_j - K + 1, B_j + 1\} 登上火车。 JOI君登上火车前往终点站后,可以在任意车站下车。
在这种情况下,JOI君希望尽可能地减少转会次数。
给定 IOI 铁路线和 JOI 君计划的信息,为每个计划编写一个程序,找出 JOI 君为实现其计划而乘坐的最少火车数量。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
N K M A_1 B_1 A_2 B_2 \vdots A_M B_M Q S_1 T_1 S_2 T_2 \vdots S_Q T_Q
出力
到标准输出 Q 行。k 行目 (1 \leqq k \leqq Q) 有JOI君
输出实现第 k 个计划的最少乘车列车数。但如果计划无法实现
输出-1 。
第
制約
- 2 \leqq N \leqq 100\,000.
- 1 \leqq K \leqq N - 1.
- 1 \leqq M \leqq 200\,000.
- 1 \leqq A_j \leqq N (1 \leqq j \leqq M).
- 1 \leqq B_j \leqq N (1 \leqq j \leqq M).
- A_j \neq B_j (1 \leqq j \leqq M).
- (A_j, B_j) \neq (A_k, B_k) (1 \leqq j < k \leqq M).
- 1 \leqq Q \leqq 50\,000.
- 1 \leqq S_k \leqq N (1 \leqq k \leqq Q).
- 1 \leqq T_k \leqq N (1 \leqq k \leqq Q).
- S_k \neq T_k (1 \leqq k \leqq Q).
- (S_k, T_k) \neq (S_l, T_l) (1 \leqq k < l \leqq Q).
小課題
- (8 点) N \leqq 300,M \leqq 300,Q \leqq 300.
- (8 点) N \leqq 2\,000,M \leqq 2\,000,Q \leqq 2\,000.
- (11 点) Q = 1.
- (25 点) K = N - 1.
- (35 点) A_j < B_j (1 \leqq j \leqq M),S_k < T_k (1\leqq k \leqq Q).
- (13 点)没有额外的限制。
入力例 1
5 2 2 5 1 3 5 3 5 3 3 2 2 1
出力例 1
1 2 -1
1 号规划是车站 它到达 5 出发 您将通过转乘多趟列车到达 3 。例如,车站 来自 5 的血统 乘坐 1 火车前往车站。 您可以在 3 下车来完成您的计划。此时搭乘的列车车次为 1 这是一本书。1 由于乘坐少于一趟列车不可能实现计划, 在线1 的 1 上输出。
2 号规划是车站 它到达 3 出发 您将通过转乘多趟列车到达 2 。例如,车站 来自 3 的血统 乘坐 2 火车前往车站。 您可以在 4 下车前往车站 在线 4 的血统 乘坐 1 火车前往车站。 您可以在 2 下车来完成您的计划。此时搭乘的列车车次为 2 这是一本书。2 由于乘坐少于一趟列车不可能实现计划, 在线2 的 2 上输出。车站 请注意,您无法登上 3 的血统 乘坐 1 火车。 它到达
3 号规划是车站
它到达 2 出发
您将通过转乘多趟列车到达 1 。既然这个计划无法实现,-1 的 3 上输出。
此输入示例是一个小作业。 1, 2, 6 满足约束。
入力例 2
6 3 2 1 6 5 1 4 5 1 6 3 3 6 2 1
出力例 2
1 -1 1 2
此输入示例是一个小作业。 1, 2, 6 满足约束。
入力例 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
此输入示例是一个小作业。 1, 2, 4, 6 满足约束。
入力例 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, 2, 5, 6 满足约束。