시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB124554446.809%

문제

복잡하고 머리 아픈 경기과학고에서의 삶에 지쳐버린 재민이는 어디론가 떠나기로 결심했다. 그렇게 재민이는 조용한 휴양지를 찾아 송죽국으로 아주 긴 여행을 떠나게 되었다.

송죽국은 $N$개의 도시가 일렬로 늘어서 있는 평화로운 국가이다. 각 도시는 가장 끝의 $1$번 도시를 기준으로 순서대로 $N$번까지의 번호를 가지고 있다.

재민이는 송죽국의 관광상품으로 유명한 송죽 열차를 타고 여행을 하려고 한다.  송죽국의 각 도시에서는 한 종류의 기차를 탈 수 있고 기차는 기차별로 정해진 선로를 따라서 운행한다.  보다 구체적으로, $i$번 도시에서 출발하는 열차는 $L_i$번 도시부터 $R_i$번 도시 사이의 도시들을 모두 지나가는 순환선으로 운영된다. $(1 \le L_i \le i \le R_i \le N)$  기차에 탄 승객은 기차가 지나가는 동안 어느 도시에서든 내릴 수 있지만 도시를 지나가는 열차에 중간에 탑승하는 것은 불가능하다.

재민이는 여행을 하며 지나갈 $Q$개의 이동 계획을 세웠다.  재민이의 $i$번째 이동 계획은 $U_i$번 도시에서 $V_i$번 도시로 송죽 열차만을 타고 이동하려는 계획이다.

재민이는 여행을 하며 시간도, 돈도 아끼고 싶기 때문에 각 이동 계획에서 최대한 적은 횟수로 열차를 갈아타려고 한다. 여러분의 할 일은 재민이를 도와 각각의 이동 계획을 열차만으로 실행할 수 있는지를, 실행할 수 있다면 타야 할 최소의 열차 수를 구하는 것이다.

입력

첫 줄에 $N, Q$가 공백을 사이에 두고 주어진다. $(1 \le N \le 200,000, 1 \le Q \le 100,000)$

이후 $N$줄에 걸쳐 $L_i, R_i$가 차례대로 공백을 사이에 두고 주어진다. $(1 \le L_i \le i \le R_i \le N)$

이후 $Q$줄에 걸쳐 $U_i, V_i$가 차례대로 공백을 사이에 두고 주어진다. $(1 \le U_i, V_i \le N)$

출력

주어진 각 이동 계획을 실행하기 위해 타야하는 최소의 열차의 수를 한 줄에 하나씩 총 $Q$줄에 출력하라.

만약 이동 계획을 열차만으로 수행할 수 없다면 -1을 열차의 수 대신 출력하라.

예제 입력 1

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

예제 출력 1

4
-1
2
0

출처

High School > 경기과학고등학교 > 나는코더다 2021 송년대회 D번