题目内容

有 $n$ 个地铁站排成一条直线，编号从 $1$ 到 $n$。有 $m$ 条地铁线路，第 $i$ 条地铁线路覆盖了 $[l_i,r_i]$ 这一段地铁站区间，$i$ 号线的地铁会在这些站之间运行。如果一个地铁站有多条地铁线路经过，就可以在这一站换乘到其他经过这一站的地铁线路。

小 A 有 $Q$ 次询问，第 $i$ 次询问给定 $s_i,t_i$，请你求出从第 $s_i$ 个地铁站到第 $t_i$ 个地铁站最少需要换乘多少次？如果无法到达则输出 $-1$。

---

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行第 $i$ 行 $2$ 个整数 $l_i,r_i$ 表示第 $i$ 条地铁线路的运行区间。

接下来一行一个整数 $Q$。

接下来 $Q$ 行第 $i$ 行两个整数 $s_i,t_i$ 表示第 $i$ 次询问。

---

输出格式

对于每次询问，输出一行一个整数表示最少需要换乘几次地铁。如果无法从 $s_i$ 到达 $t_i$，输出 -1。

---

样例输入1

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

---

样例输出1

2
0
1

---

样例输入2

10 5
1 3
2 5
6 7
7 9
9 10
5
1 5
7 2
8 7
3 5
6 10

---

样例输出2

1
-1
0
0
2

---

提示

【样例解释】

对于样例 1 的第 3 组询问，可以先坐 2 号线路从 2 号站到 5 号站，然后转乘 3 号线路从 5 号站坐到 6 号站，只需要转站一次。

对于样例 2 的第 2 组询问，注意到没有任何地铁线路跨过 5 号站到 6 号站这一区间，所以不可能从 7 号站到达 2 号站，输出 $-1$。

【数据范围】

对于 $20\%$ 的数据，$n,m,Q\le 2\times10^3$。

对于 $40\%$ 的数据，$n,m\le 2\times 10^3$。

对于 $100\%$ 的数据，$2\le n\le 5\times10^5$，$1\le m\le 10^6$，$1\le Q\le 5\times10^5$，$1\le l_i< r_i\le n$，$1\le s_i,t_i\le n$，$s_i \neq t_i$。

注意不保证 $s_i< t_i$，也就是说可能出现 $s_i>t_i$，即需要从编号较大的站坐到编号较小的站。

---

大佬神犇们球球了qwq