题目描述

给定一张 $N$ 个点 $M$ 条边的无向连通图，然后执行 $Q$次操作，每次向图中添加一条边，并且询问当前无向图中“桥”的数量。

输入格式

输入包含多组测试数据。

每组测试数据，第一行包含两个整数 $N$ 和 $M$。

接下来$M$ 行，每行包含两个整数 $A$和$B$，表示点 $A$ 和点$B$ 之间有一条边，点的编号为 1∼$N$。

接下来一行，包含整数 $Q$。

在接下来 $Q$ 行，每行包含两个整数 $A$ 和 $B$，表示在 $A$ 和$B$之间加一条边。

当输入 0 0 时表示输入终止。

输出格式

每组数据第一行输出 Case x:，其中 $x$为组别编号，从 1 开始。

接下来v Q $行，每行输出一个整数，表示一次询问的结果。

每组数据输出完毕后，输出一个空行。

样例

3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0

Case 1:
1
0

Case 2:
2
0

数据范围

• $1≤N≤100000$
• $N−1≤M≤200000, 1≤A≠B≤N,1≤Q≤1000$

来源

• POJ3694
• 算法竞赛进阶指南