시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB143423327.500%

문제

What a strange coincidence! After having determined the most valuable contemporary art collection, you noticed that it is apparently located somewhere near Lübeck. Since you don’t know its exact location, you want to gather more information. Luckily, on the day you arrive for this year’s BOI, the local art community hosts $N$ events about contemporary art. This seems to be just the opportunity you were waiting for.

To plan your visit of these events, you numbered them from $1$ to $N$ with the $i$-th event starting at time $S_i$ and ending at time $E_i$. You want to start your visit by attending some event $s$ and finish your visit at some event $e$. As long as you are not attending event $e$, you will always attend your current event until the end* and then immediately switch to a different event that is currently running. This means that you can switch from event $i$ to event $j$ if and only if $S_j ≤ E_i ≤ E_j$.

Obviously, switching events too frequently would make you look suspicious. Thus, you want to determine the minimum number of event switches necessary if you start at event $s$ and finish at $e$. Moreover, since you do not yet know when you will arrive in Lübeck and when you will have to leave for the BOI registration in the evening, you want to determine this for $Q$ different pairs of starting and ending events $s$ and $e$.


* It would be rude to leave earlier—though nobody will complain about you being late as you are obviously an important and busy art critic.

입력

The first line of input contains two integers, the number of events $N$ and the number of pairs of events $Q$ for which you want to determine the minimum number of event switches.

Then, $N$ lines follow describing the events. The $i$-th of these lines contains two integers $S_i$ and $E_i$, the starting and ending time of event $i$.

Then, $Q$ lines follow describing the queries. The $i$-th of these lines contains two integers $s_i$ and $e_i$, meaning that you want to determine the minimum number of event switches necessary if you want to start at event $s_i$ and end your visit at event $e_i$.

출력

Your program should output $Q$ lines. The $i$-th of these lines should consist of an integer, the minimum number of event switches necessary if you start at event $s_i$ and end your visit at event $e_i$, or the string impossible if there is no way to achieve this.

제한

We always have $1 ≤ N, Q ≤ 100\,000$, $1 ≤ S_i < E_i ≤ 10^9$, and $1 ≤ s_i, e_i ≤ N$.

서브태스크

번호배점제한
110

For every event, you can switch to at most one other event.

210

$N ≤ 1\,000$ and $Q ≤ 100$

315

$N ≤ 5\,000$

415

$Q ≤ 100$

520

No event is completely contained in another event, i.e. there are no two events $i \ne j$ with $S_i ≤ S_j < E_j ≤ E_i$.

630

No further constraints.

예제 입력 1

5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2

예제 출력 1

2
impossible

예제 입력 2

8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8

예제 출력 2

3
4
impossible
0
impossible

힌트

In the first example, it is possible to start at event $1$ and end at event $4$ by switching from event $1$ to event $5$ and then to event $4$, resulting in two event switches. However, there is no way to start at event $3$ and end at event $2$ because event $2$ ends before event $3$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.