题目描述

题目译自 BalticOI 2022 Day1「Event Hopping」

有 $n$ 个区间，第 $i$ 个区间为 $[l_i, r_i]$。

你可以在区间之间跳跃。当你在第 $x$ 个区间上时，你可以跳到一个覆盖右端点 $r_x$ 的区间 $y$ 上，即从 $x$ 能跳到 $y$ 当且仅当 $r_x \in [l_y, r_y]$。

有 $q$ 次询问，每次你一开始在第 $s_i$ 个区间，你需要跳到第 $t_i$ 个区间。你需要输出你至少需要跳多少次。如果不能跳到，输出 impossible。

---

输入格式

第一行，两个整数 $n, q$。

接下来 $n$ 行，每行两个整数 $l_i, r_i$。

接下来 $q$ 行，每行两个整数 $s_i, t_i$。

---

输出格式

输出 $q$ 行，第 $i$ 行输出第 $i$ 次询问的答案。如果无解输出 impossible。

---

样例 1

输入

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

输出

2
impossible

解释
第一次询问中，一种可行的跳跃方案是 $1 \rightarrow 5 \rightarrow 4$，共跳跃两次。
第二次询问中，由于第 $3$ 个区间的右端点已经在第 $2$ 个区间右端点右边，所以不存在跳跃的方案。

---

样例 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

输出

3
4
impossible
0
impossible

---

数据范围与提示

• 子任务 1（$10$ 分）：每一个区间可以跳到至多一个其他区间。
• 子任务 2（$10$ 分）：$N \leq 1000, Q \leq 100$。
• 子任务 3（$15$ 分）：$N \leq 5000$。
• 子任务 4（$15$ 分）：$Q \leq 100$。
• 子任务 5（$20$ 分）：不存在两个区间 $i,j$ 满足 $[l_i,r_i] \subseteq [l_j,r_j]$。
• 子任务 6（$30$ 分）：没有特殊限制。

对于所有数据，满足：

$$1 < N, Q < 100000,\quad 1 < l_i < r_i < 10^9,\quad 1 \leq s_i, t_i \leq n $$