问题 D：地铁站
文件提交：文件名：esubway
内存限制：512 MB
时间限制：3.000 S
评测方式：普通裁判
金币值：
命题人：
提交：81
解决：0
题目描述
## 题目描述
有 $n$ 个地铁站排成一条直线，编号从 $1$ 到 $n$。有 $m$ 条地铁线路，第 $i$ 条地铁线路覆盖了 $[l_i,r_i]$ 这一段地铁站区间，$i$ 号线的地铁会在这些站之间运行。如果一个地铁站有多条地铁线路经过，就可以在这一站换乘到其他经过这一站的地铁线路。
小 Z 有 $Q$ 次询问，第 $i$ 次询问给定 $s_i,t_i$，请你求出从第 $s_i$ 个地铁站到第 $t_i$ 个地铁站最少需要**换乘**多少次？如果无法到达则输出 $-1$。
- 注意，本题要求输出的是换乘的次数，如果从起点可以直接做一条线路直达终点，那么中间没有换乘，应该输出 `0`。
## 输入格式
第一行两个整数 $n,m$。
接下来 $m$ 行，第 $i$ 行 $2$ 个整数 $l_i,r_i$ 表示第 $i$ 条地铁线路的运行区间。
接下来一行一个整数 $Q$。
接下来 $Q$ 行第 $i$ 行两个整数 $s_i,t_i$ 表示第 $i$ 次询问。
## 输出格式
对于每次询问，输出一行一个整数表示最少需要换乘几次地铁。如果无法从 $s_i$ 到达 $t_i$，输出 `-1`。
## 样例
**输入1**
```
10 4
1 4
3 8
7 9
4 9
3
1 10
1 9
3 7
```
**输出1**
```
-1
1
0
```
### 样例2
查看大样例 2 的输入数据和输出数据。
### 样例3
查看大样例 3 的输入数据和输出数据。
## 说明/提示
### 样例 1 解释
第一次询问，显然无法到达 $10$ 号站，因此输出 `-1`。
第二次询问，小 Z 从 $1$ 号站坐地铁到 $4$ 号站，然后换乘从 $4$ 坐到 $9$ 换乘了一次。
第三次询问，小 Z 可以从 $3$ 直达 $7$，不需要换乘。
### 数据范围
- 对于 $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$，即需要从编号较大的站坐到编号较小的站。