J11 实践-4 可靠的网络

题目描述

我们已经知道 $\text{Polycarpus}$ 担任系统管理员的大公司。那里的计算机网络由 $n$ 台计算机和 $m$ 根连接一对计算机的电缆组成。换言之，计算机网络可以表示为具有 $n$ 个节点和 $m$ 条边的无向图。让我们用 $1$ 到 $n$ 的整数来给计算机编号，用 $1$ 到 $m$ 的整数来给电缆编号。

$\text{Polycarpus}$ 被赋予一项重要任务——检查公司网络的可靠性。为此， $\text{Polycarpus}$ 决定在计算机网络上进行 $k$ 实验，其中第 $i$ 个实验如下：

（1）暂时断开从 编号 $l_i$ 到 $r_i$ （包含两端）的电缆（其他电缆保持连接）。

（2）计算此时计算机网络的中连通块的数量。

（3）将断开的电缆重新连接（即恢复初始网络）。

帮助 $\text{Polycarpus}$ 执行所有实验，并为每个实验输断开电缆后连通块的数量。孤立节点应也计为一个连通块。

输入格式

第一行包含两个空格分隔的整数 $n$，$m$，分别对应计算机的数量和电缆的数量。

往下 $m$ 行包含电缆的说明。

第 $i$ 行含有一对整数 $x_i,y_i$,表示第 $i$ 根电缆连接的计算机编号。请注意，一对计算机可以通过多条电缆连接。

下一行包含整数 $k$，对应实验的次数。

接下来的 $k$ 行包含实验的描述。第 $i$ 行包含空格分隔的整数 $l_i,r_i$-第 $i$ 次实验期间 $\text{Polycarpus}$ 断开的电缆范围。

输出格式

输出 $k$ 行，每行一个整数，表示在第 $i$ 个实验期间定义计算机网络的连通块数量。

输入样例

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

输出样例

4
5
6
3
4
2

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$2 \le n \le 500$，$0 \le m \le 10^4$，$1 \le x_i, y_i \le n$，$x_i \neq y_i$，$1 \le k \le 2 \times 10^4$，$1 \le l_i, r_i \le m$。