给定一张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行，每行输出一个整数，表示一次询问的结果。

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

数据范围

$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

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解