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$).