Minimizing Train Rides Under Boarding Restrictions

IOI Rail Company operates trains on a single straight track with N stations numbered from 1 to N in order. Two consecutive stations are connected directly by a rail. The company runs M train routes. For each route j, the train starts at station \(A_j\) and goes to station \(B_j\). If \(A_j B_j\) the train stops at every station \(A_j, A_j-1, \dots, B_j\>.

JOI, a weary traveler, has Q travel plans. In the kth plan he wishes to go from station \(S_k\) to station \(T_k\) by taking one or more trains. However, to ensure a seat for resting, he decides that he will only board a train on a station that is among the first K stops of that route. More formally, consider a route \(j\):

• If \(A_j < B_j\) (forward route), he is willing to board at station \(i\) only if \(A_j \le i \le \min\{A_j+K-1, B_j-1\}\).
• If \(A_j > B_j\) (backward route), he is willing to board at station \(i\) only if \(\max\{A_j-K+1, B_j+1\} \le i \le A_j\).

After boarding a train, he may disembark at any subsequent station along that train's route. Note that he cannot change trains mid-route – each train ride counts as one ride. JOI wishes to minimize the number of train rides required to complete his journey. If it is impossible to reach the destination using the available routes under the boarding restrictions, output \(-1\).

Input Format: The input begins with a line containing three integers N, M and K. The following M lines each contain two integers \(A_j\) and \(B_j\) describing a train route. Then a line containing the integer Q follows, and the following Q lines each contain two integers \(S_k\) and \(T_k\) representing a travel plan.

Output Format: For each travel plan output the minimum number of train rides needed. If a travel plan is impossible, output \(-1\) for that case.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains three integers N, M and K.

Then M lines follow, each with two integers \(A_j\) and \(B_j\) (\(1 \leq j \leq M\)).

The next line contains an integer Q, the number of travel plans.

The next Q lines each contain two integers \(S_k\) and \(T_k\) (\(1 \leq k \leq Q\)).

outputFormat

Output Q lines. The \(k\)th line should contain the minimum number of train rides required for the \(k\)th travel plan, or \(-1\) if it is impossible to reach the destination.

sample

5 2 2
1 5
5 1
3
1 5
1 4
4 1

1
1
1