Problem Description

There are $n$ intervals. The $i$-th interval is $[l_i, r_i]$.

You can hop between intervals. When you are at interval $x$, you can hop to an interval $y$ that covers the right endpoint $r_x$, i.e., you can hop from $x$ to $y$ if and only if $r_x \in [l_y, r_y]$.

There are $q$ queries. In each query, you start at interval $s_i$ and need to hop to interval $t_i$. You need to output the minimum number of hops required. If it is impossible to reach it, output impossible.

Input Format

The first line contains two integers $n, q$.

The next $n$ lines each contain two integers $l_i, r_i$.

The next $q$ lines each contain two integers $s_i, t_i$.

Output Format

Output $q$ lines. On the $i$-th line, output the answer to the $i$-th query. If there is no solution, output impossible.

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

2
impossible

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

3
4
impossible
0
impossible

Hint

• Subtask $1$ ($10$ points): Each interval can hop to at most one other interval.
• Subtask $2$ ($10$ points): $n \le 1000$, $q \le 100$.
• Subtask $3$ ($15$ points): $n \le 5000$.
• Subtask $4$ ($15$ points): $q \le 100$.
• Subtask $5$ ($20$ points): There do not exist two intervals $i, j$ such that $[l_i, r_i] \subseteq [l_j, r_j]$.
• Subtask $6$ ($30$ points): No special constraints.

For all testdata, $1 \le n, q \le 100000$, $1 \le l_i < r_i \le 10^9$, $1 \le s_i, t_i \le n$.

Translated by ChatGPT 5