← 返回题目列表

AtCoder · joi2022ho_d

D. 铁路之旅2

中文机器翻译题面 查看原题

配点: 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).

小課題

  1. (8 点) N \leqq 300,M \leqq 300,Q \leqq 300.
  2. (8 点) N \leqq 2\,000,M \leqq 2\,000,Q \leqq 2\,000.
  3. (11 点) Q = 1.
  4. (25 点) K = N - 1.
  5. (35 点) A_j < B_j (1 \leqq j \leqq M),S_k < T_k (1\leqq k \leqq Q).
  6. (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 满足约束。