24477번 - Railway Trip 2 서브태스크다국어

문제

IOI Railway Company is operating lines on a railway track. There are $N$ stations in a straight line, numbered from 1ドル$ to $N$. For each $i$ (1ドル ≤ i ≤ N - 1$), Station $i$ and Station $i + 1$ are connected directly by a railway track.

IOI Railway Company is operating $M$ lines, numbered from 1ドル$ to $M$. In Line $j$ (1ドル ≤ j ≤ M$), the starting station is Station $A_j,ドル and the terminal station is Station $B_j$. A train stops at every station. Namely, if $A_j < B_j$ a train of Line $j$ stops at Station $A_j,ドル Station $A_j + 1,ドル $\dots,ドル Station $B_j,ドル in this order. If $A_j > B_j,ドル a train of Line $j$ stops at Station $A_j,ドル Station $A_j - 1,ドル $\dots,ドル Station $B_j,ドル in this order.

JOI-kun is a traveler. He has $Q$ travel plans. In the $k$-th plan (1ドル ≤ k ≤ Q$), he travels from Station $S_k$ to Station $T_k$ by taking lines.

However, JOI-kun is tired from a long journey. He wants to take a vacant train and get a seat. Thus, JOI-kun decided that he takes a train of a line at a station only if it is the $K$-th or earlier stop from the starting station of the line. In other words, if $A_j < B_j,ドル he can take a train of Line $j$ only at Station $A_j,ドル Station $A_j + 1,ドル $\dots,ドル Station $\min{\{A_j + K - 1, B_j - 1\}}$. If $A_j > B_j,ドル he can take a train of Line $j$ only at Station $A_j,ドル Station $A_j - 1,ドル $\dots,ドル Station $\max{\{A_j - K + 1, B_j + 1\}}$. JOI-kun will get out of the train at a station between the station next to where he takes the train and the terminal station, inclusive.

Under these conditions, JOI-kun wants to minimize the number of times of taking trains.

Given the information of the lines of IOI Railway Company and JOI-kun’s plans, write a program which calculates, for each of JOI-kun’s plans, the minimum number of times of taking trains needed for JOI-kun to achieve it.

입력

Read the following data from the standard input. Given values are all integers.

$\begin{align*}&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\end{align*}$

출력

Write $Q$ lines to the standard output. The $k$-th line (1ドル ≤ k ≤ Q$) should contain the minimum number of times of taking trains needed for JOI-kun to achieve the $k$-th plan. If it is not possible to achieve the $k$-th plan, output -1.

제한

• 2ドル ≤ N ≤ 100,000円$.
• 1ドル ≤ K ≤ N - 1$.
• 1ドル ≤ M ≤ 200,000円$.
• 1ドル ≤ A_j ≤ N$ (1ドル ≤ j ≤ M$).
• 1ドル ≤ B_j ≤ N$ (1ドル ≤ j ≤ M$).
• $A_j \ne B_j$ (1ドル ≤ j ≤ M$).
• $(A_j , B_j) \ne (A_k, B_k)$ (1ドル ≤ j < k ≤ M$).
• 1ドル ≤ Q ≤ 50,000円$.
• 1ドル ≤ S_k ≤ N$ (1ドル ≤ k ≤ Q$).
• 1ドル ≤ T_k ≤ N$ (1ドル ≤ k ≤ Q$).
• $S_k \ne T_k$ (1ドル ≤ k ≤ Q$).
• $(S_k, T_k) \ne (S_l , T_l)$ (1ドル ≤ k < l ≤ Q$).

서브태스크

힌트