CF292D Connected Components

我们已经知道 Polycarpus 在一家大型公司担任系统管理员。这家公司的计算机网络由 $n$ 台计算机和 $m$ 根电缆组成，这些电缆连接着某些计算机对。换句话说，计算机网络可以用一个无向图来表示，包含 $n$ 个结点和 $m$ 条边。我们将计算机按 1 到 $n$ 编号，将电缆按 1 到 $m$ 编号。 Polycarpus 收到了一个重要任务——检查公司网络的可靠性。为此，Polycarpus 决定对计算机网络进行 $k$ 组实验，每组实验的具体过程如下： 1. 暂时断开编号从 $l_{i}$ 到 $r_{i}$ 的电缆（包含两端），其余电缆保持连接。 2. 在此时刻，统计此网络对应的图中连通块的数量。 3. 重新连接刚才断开的编号从 $l_{i}$ 到 $r_{i}$ 的电缆（恢复到初始网络）。 请你帮助 Polycarpus 完成所有实验，并为每次实验输出断开上述区间电缆后计算机网络中连通块的数量。孤立点也应算作一个连通块。

第一行包含两个用空格分隔的整数 $n, m$ $(2 \leq n \leq 500; 1 \leq m \leq 10^{4})$，分别表示计算机数量和电缆数量。 接下来的 $m$ 行，每行包含两个用空格分隔的整数 $x_i, y_i$ $(1 \leq x_i, y_i \leq n; x_i \neq y_i)$，表示第 $i$ 根电缆连接的两台计算机编号。注意，同一对计算机之间可能有多根电缆。 随后的第一行包含一个整数 $k$ $(1 \leq k \leq 2 \times 10^4)$，表示实验的数量。 之后的 $k$ 行，每行包含两个用空格分隔的整数 $l_i, r_i$ $(1 \leq l_i \leq r_i \leq m)$，表示 Polycarpus 在第 $i$ 次实验中断开的电缆编号区间。

输出 $k$ 个整数，第 $i$ 个整数表示在第 $i$ 次实验中（断开相应区间电缆后）网络中连通块的数量。

由 ChatGPT 5 翻译