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