철도 여행 2

IOI 철도 회사는 하나의 철도 노선 위에서 여러 열차를 운행한다. 일직선 위에 $N$개의 역이 있고, $1$번부터 $N$번까지 번호가 붙어 있다. 각 $i$ ($1 ≤ i ≤ N - 1$)에 대해 $i$번 역과 $i + 1$번 역은 철도로 직접 연결되어 있다.

IOI 철도 회사는 $M$개의 열차를 운행하며, $1$번부터 $M$번까지 번호가 붙어 있다. $j$번 열차 ($1 ≤ j ≤ M$)의 출발역은 $A\_j$번 역이고 종착역은 $B\_j$번 역이다. 열차는 모든 역에 정차한다. 즉 $A\_j < B\_j$이면 $j$번 열차는 $A\_j$번 역, $A\_j + 1$번 역, $\dots$, $B\_j$번 역 순서로 정차한다. $A\_j > B\_j$이면 $j$번 열차는 $A\_j$번 역, $A\_j - 1$번 역, $\dots$, $B\_j$번 역 순서로 정차한다.

JOI군은 여행자이다. 그는 $Q$개의 여행 계획을 세웠다. $k$번째 계획 ($1 ≤ k ≤ Q$)에서 그는 $S\_k$번 역에서 $T\_k$번 역까지 열차를 갈아타며 이동한다.

그런데 JOI군은 긴 여행에 지쳐 있다. 그는 빈 열차를 타고 자리에 앉고 싶다. 그래서 JOI군은 어떤 역에서 열차를 탈 때, 그 열차의 출발역에서 $K$번째 정차역까지만 탈 수 있기로 했다. 다시 말해 $A\_j < B\_j$이면 $j$번 열차는 $A\_j$번 역, $A\_j + 1$번 역, $\dots$, $\min{\{A\_j + K - 1, B\_j - 1\}}$번 역에서만 탈 수 있다. $A\_j > B\_j$이면 $j$번 열차는 $A\_j$번 역, $A\_j - 1$번 역, $\dots$, $\max{\{A\_j - K + 1, B\_j + 1\}}$번 역에서만 탈 수 있다. JOI군은 탄 역의 다음 역부터 종착역까지 중 한 역에서 내린다.

이 조건에서 JOI군은 열차를 타는 횟수를 최소화하려 한다.

IOI 철도 회사의 열차 정보와 JOI군의 계획이 주어졌을 때, 각 계획마다 JOI군이 그 계획을 달성하는 데 필요한 최소 열차 탑승 횟수를 계산하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.

\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\*}

표준 출력에 $Q$개의 줄을 출력한다. $k$번째 줄 ($1 ≤ k ≤ Q$)에는 JOI군이 $k$번째 계획을 달성하는 데 필요한 최소 열차 탑승 횟수를 출력한다. $k$번째 계획을 달성할 수 없으면 -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$).