问题2545--网络(network)

2545: 网络(network)

时间限制: 2 Sec  内存限制: 128 MB
提交: 39  解决: 20
[提交] [状态] [讨论版] [命题人:]

题目描述

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

输入

输入包含多组测试数据。
每组测试数据,第一行包含两个整数N和M。
接下来M行,每行包含两个整数A和B,表示点A和点B之间有一条边,点的编号为1~N。
接下来一行,包含整数Q。
在接下来Q行,每行包含两个整数A和B,表示在A和B之间加一条边。
当输入0 0时表示输入终止。

输出

每组数据第一行输出“Case x:”,其中x为组别编号,从1开始。
接下来Q行,每行输出一个整数,表示一次询问的结果。
每组数据输出完毕后,输出一个空行。

样例输入 Copy

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

样例输出 Copy

Case 1:
1
0

Case 2:
2
0

提示

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