← 返回题目列表

Codeforces · 292/D

D. 连接的组件

中文机器翻译题面 查看原题

我们已经知道 Polycarpus 在一家大公司担任系统管理员。那里的计算机网络由n台计算机和m条连接一些计算机对的电缆组成。换句话说,计算机网络可以表示为一些具有 n 个节点和 m 个边的无向图。让我们用 1 到 n 的整数来索引计算机,用 1 到 m 的整数来索引电缆。

Polycarpus 被赋予了一项重要任务——检查公司网络的可靠性。为此,Polycarpus 决定在计算机网络上进行一系列 k 次实验,其中第 i 个实验如下:

1. 暂时断开索引为 li 到 ri(含 li 和 ri)的电缆(其他电缆保持连接)。
2. 计算当时定义计算机网络的图中连接组件的数量。
3. 重新连接索引为li 至ri 的断开线缆(即恢复初始网络)。

帮助 Polycarpus 进行所有实验,并为每个实验打印图中通过给定实验定义计算机网络的连接组件的数量。孤立的顶点应算作单个组件。

输入

第一行包含两个以空格分隔的整数 n, m (2 ≤ n ≤ 500; 1 ≤ m ≤ 104) — 相应的计算机数量和电缆数量。

以下 m 行包含电缆的描述。第 i 行包含以空格分隔的一对整数 xi, yi (1 ≤ xi, yi ≤ n; xi ≠ yi) — 通过第 i 根电缆连接的计算机的编号。请注意,一对计算机可以通过多条电缆连接。

下一行包含整数 k (1 ≤ k ≤ 2·104) — 实验次数。接下来的 k 行包含实验的描述。第 i 行包含空格分隔的整数 li, ri (1 ≤ li ≤ ri ≤ m) — Polycarpus 在第 i 个实验中断开的电缆数量。

输出

打印 k 个数字,第 i 个数字表示第 i 个实验期间定义计算机网络的图的连通分量的数量。

示例

输入 #1

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

输出 #1

4
5
6
3
4
2