鉄道旅行2 (Railway Trip 2)

IOI 鉄道は1 本の鉄道路線を運営している.IOI 鉄道線には一直線上に並んだN 個の駅があり,1 からN
までの番号が付けられている.各i (1 ≦i ≦N −1) に対して,駅i と駅i + 1 の間は線路で結ばれている.
IOI 鉄道線にはM 系統の運行系統があり,1 からM までの番号が付けられている.系統j (1 ≦j ≦M) の
列車の始発駅は駅Aj であり,終着駅は駅Bj である.列車は各駅に停車する.すなわち,系統j の列車は,
Aj < Bj のとき駅Aj,駅Aj + 1,... ,駅Bj の順に停車し,Aj > Bj のとき駅Aj,駅A j −1,... ,駅Bj の
順に停車する.
旅人のJOI くんは,Q 個の旅行計画を考えている.k 番目(1 ≦k ≦Q) の計画は,駅S k から出発し,駅
Tk にいくつかの列車を乗り継いで到着するというものである.
しかしながら,JOI くんは長旅で疲れているので,空いている列車に乗車し,着席したい.そのため,
JOI くんがある列車に乗車するのは,その列車の始発駅から(始発駅を含めて)K 駅以内の駅からのみと
した.すなわち,JOI くんが系統j の列車に乗車するとき,Aj < Bj であれば駅Aj,駅A j + 1,. .. ,駅
min{Aj + K −1, Bj −1} から乗車でき,Aj > Bj であれば駅Aj,駅Aj −1,... ,駅max{Aj −K + 1, Bj + 1}
から乗車できる.JOI くんは,列車に乗車した駅の次の駅からその列車の終着駅までの各駅のうちいずれか
の駅で下車する.
JOI くんはこの条件のもと,なるべく乗り継ぎの回数を少なくしたい.
IOI 鉄道線の情報とJOI くんの計画が与えられたとき,それぞれの計画について,JOI くんが計画を達成
するために乗車する列車の数の最小値を求めるプログラムを作成せよ.

第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)

• 2 ≦N ≦100 000.
• 1 ≦K ≦N −1.
• 1 ≦M ≦200 000.
• 1 ≦Aj ≦N (1 ≦j ≦M).
• 1 ≦Bj ≦N (1 ≦j ≦M).
• Aj , Bj (1 ≦j ≦M).
• (Aj, Bj) , (Ak, Bk) (1 ≦j < k ≦M).
• 1 ≦Q ≦50 000.
• 1 ≦S k ≦N (1 ≦k ≦Q).
• 1 ≦Tk ≦N (1 ≦k ≦Q).
• S k , Tk (1 ≦k ≦Q).

第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)
• (S k, Tk) , (S l, Tl) (1 ≦k < l ≦Q).

1. (8 点) N ≦300,M ≦300,Q ≦300.
2. (8 点) N ≦2 000,M ≦2 000,Q ≦2 000.
3. (11 点) Q = 1.
4. (25 点) K = N −1.
5. (35 点) A j < Bj (1 ≦j ≦M),S k < Tk (1 ≦k ≦Q).
6. (13 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N K
M
A1 B1
A2 B2
...
AM BM
Q
S 1 T1
S 2 T2
...
S Q TQ

標準出力にQ 行で出力せよ.k 行目(1 ≦k ≦Q) には,JOI くんがk 番目の計画を達成するために乗車す
る列車の数の最小値を出力せよ.ただし,計画が達成不可能な場合は,-1 を出力せよ.

생성자가 기록되지 않았습니다.

출처 JOI 2022 Final