P8391 [BalticOI 2022] Event Hopping (Day1)

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`.

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 $q$ lines. On the $i$-th line, output the answer to the $i$-th query. If there is no solution, output `impossible`.

- 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