题目描述

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

输入格式

输入包含多组测试数据。

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

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

接下来一行，包含整数$\red {Q}$。

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

当输入$\red {0 ~0}$时表示输入终止。

输出格式

每组数据第一行输出$\red {“Case~ x:”}$，其中$\red {x}$为组别编号，从$\red {1}$开始。

接下来$\red {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

提示

$\red {1≤N≤100000}$

$\red {N−1≤M≤200000}$,

$\red {1≤A≠B≤N}$,

$\red {1≤Q≤1000}$