鉄道旅行 2 (Railway Trip 2)

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\) 点) 追加の制約はない．

JOI 2022 · JCIOI · CC BY-SA 4.0