문제
정올국에는 1~N번까지의 번호가 순서대로 붙어있는 N개의 역이 있다.
i번 역과 i+1번 역 사이에는 철로가 깔려있다.
주식회사 박재민은 이 역들을 지나는 M개의 기차 노선을 운영하고 있다. j번 노선은 A_j 번 역에서 출발해 B_j번 역까지 운행한다.
A_j < B_j 라면 기차는 A_j, A_j + 1, ... , B_j번 역을 차례대로 지나고, 그 반대라면 기차는 A_j, A_j - 1, ... , B_j번 역을 차례대로 지난다.
기차는 항상 지나는 모든 역에서 정차하고 승객은 어느 역에서든 내릴 수 있다.
준혁이는 여행자이다. 준혁이는 Q개의 여행 계획을 가지고 있다.
준혁이의 k번째 여행 계획은 S_k번 역에서 T_k번 역으로 기차를 타고 이동하는 것이다.
하지만 준혁이는 연약하고 지쳐 기차에 앉아서 가고 싶어한다.
따라서 준혁이는 어떤 노선이든 시작역으로부터 K번째 이내인 역에서만 승차해 빈 자리를 사수할 계획이다.
보다 정확히, A_j < B_j라면 준혁이는 A_j, A_j + 1, ... , min{A_j + K - 1, B_j + 1}에서만 j번 노선에 탑승할 것이고,
A_j > B_j라면 준혁이는 A_j, A_j - 1, ... , min{A_j - K + 1, B_j + 1}에서만 j번 노선에 탑승할 것이다.
준혁이는 이런 조건을 지키면서 각 여행계획마다 역들 사이를 이동하는 방법을 알고 싶다.
연약한 준혁이는 기차를 갈아타는 횟수를 최소화 하고 싶어한다. 여러분이 준혁이를 도와주자!
입력
표준입력으로 아래의 정보들이 주어진다. 모든 주어지는 값은 정수이다.
N K
M
A_1 B_1
A_2 B_2
...
A_M B_M
Q
S_1 T_1
S_2 T_2
...
S_Q T_Q
(제한 조건)
- 2 <= N <= 100000
- 1 <= K <= N-1
- 1 <= M <= 200000
- 1 <= A_j <= N
- 1 <= B_j <= N
- A_j != B_j
- (A_j, B_j) != (A_k, B_k)
- 1 <= Q <= 50000
- 1<= S_k <= N
- 1 <= T_k <= N
- S_k != T_k
- (S_k, T_k) != (S_l, T_l)
(서브태스크)
#1 (8점) : N <= 300, M <= 300, Q <= 300
#2 (8점) : N <= 2000, M <= 2000, Q <= 2000
#3 (11점) : Q = 1
#4 (25점) : K = N-1
#5 (35점) : A_j < B_j, S_k < T_k
#6 (13점) : 추가적인 제약조건이 없다.
출력
Q줄에 걸쳐 줄마다 준혁이의 여행계획을 위해 타야하는 최소의 기차의 수를 출력하라.
만약, 불가능한 이동 계획이라면 -1을 출력하라.
예제1
52
2
51
35
3
53
32
21
1
2
-1
예제2
63
2
16
51
4
51
63
36
21
1
-1
1
2