电脑网络

题目描述:

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

输入格式:

输入包含多组测试数据。

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

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

接下来一行，包含整数 \(Q\)。

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

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

输出格式:

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

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

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

数据范围:

\(1 \le N \le 100000\),

\(N-1 \le M \le 200000\),

\(1 \le A \neq B \le N\),

\(1 \le Q \le 1000\)

样例输入:

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

提示:

N<=10⁵，M<=2*10⁵，Q<=1000。

算法提示：

无向图连通块，缩点。

时间限制: 1000ms
空间限制: 256MB

---