屏障
时间限制：3秒
内存限制：512 MB
输入：标准输入
输出：标准输出
题目描述
在魔法世界中，存在一个由能量屏障和连接它们的能量走廊组成的网络。每个屏障对应图中的一个顶点，每条走廊对应一条边。已知该网络不含环，即不能在不重复经过同一条边的情况下从一个屏障出发回到自身。
在一次夜间能量爆发后，东京的屏障被撕裂成若干独立碎片。五条悟给你一个屏障区间 $[l, r]$，请你求出该区域分裂成了多少个独立连通块。
独立连通块定义为该区域中一个极大的子集，在该子集内，可以通过能量走廊从任意一个屏障到达另一个屏障，且不超出区域（区间 $[l, r]$）。如果区域内两组屏障之间没有走廊连接，则它们属于不同的连通块：必须分别隔离和清除。
目前威胁尚在远方，因此你需要处理 $q$ 个询问，对每个区间 $[l, r]$ 输出连通块的数量。
输入格式
第一行包含两个整数 $n$ 和 $m$ —— 屏障的数量和能量走廊的数量（$0 \le m < n \le 5 \cdot 10^5$）。
接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ —— 第 $i$ 条走廊连接的两个屏障的编号（$1 \le u, v \le n$；$u \neq v$）。
下一行包含一个整数 $q$ —— 询问的数量（$1 \le q \le 2 \cdot 10^5$）。
接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$ —— 询问的描述（$1 \le l \le r \le n$）。
保证图不含环、自环和重边。
输出格式
输出 $q$ 行，每行一个整数表示对应询问的答案。
评分系统
只有通过某个子任务及其所有必需子任务的全部测试，才能获得该子任务的分值。
| 子任务 | 分值 | 附加限制 | 必需子任务 | 评测信息 |
|---|---|---|---|---|
| 0 | – | 样例 | 无 | 完全 |
| 1 | 5 | $m = 0$ | 无 | 首次错误 |
| 2 | 10 | $n, q \le 1\,000$ | 0 | 首次错误 |
| 3 | 18 | $m, q \le 5\,000$ | 0, 2 | 首次错误 |
| 4 | 5 | $r_i - l_i \le 10$；$q \le 50\,000$ | 无 | 首次错误 |
| 5 | 7 | $n \le 10\,000$；$v_i = u_i + 1$ | 无 | 首次错误 |
| 6 | 8 | $v_i = u_i + 1$ | 5 | 首次错误 |
| 7 | 9 | $n \le 10\,000$ | 0, 5 | 首次错误 |
| 8 | 8 | 每个屏障至多与一个屏障相连 | 无 | 首次错误 |
| 9 | 11 | $n, q \le 10^5$ | 0, 2 | 首次错误 |
| 10 | 19 | 无 | 0–9 | 首次错误 |
表格中所有 $v_i$、$u_i$、$l_i$ 和 $r_i$ 的限制均适用于所有 $i$。
样例
样例 #1
输入数据：
7 5
1 2
2 3
4 5
5 6
6 7
5
1 3
1 4
2 5
3 6
5 7输出数据：
1
2
2
2
1样例 #2
输入数据：
8 5
1 4
2 4
4 7
3 5
6 8
4
1 2
1 4
3 7
6 8输出数据：
2
2
3
2