|
|
#include <cstdio>
|
|
|
#include <iostream>
|
|
|
#include <algorithm>
|
|
|
#include <cstring>
|
|
|
|
|
|
using namespace std;
|
|
|
const int M = 400010;
|
|
|
const int N = 100010;
|
|
|
|
|
|
int bridge[N]; // 某个节点的入边是不是桥,比如 u->v是桥，则记录bridge[v]=1
|
|
|
int p[N]; // 并查集
|
|
|
int bcnt; // 桥的数量
|
|
|
|
|
|
int n, m;
|
|
|
// 链式前向星
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
// Tarjan算法求割边模板
|
|
|
int dfn[N], low[N], ts;
|
|
|
void tarjan(int u, int fa) {
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (v == fa) continue;
|
|
|
|
|
|
if (!dfn[v]) {
|
|
|
p[v] = u; // 记录v的父节点是u
|
|
|
tarjan(v, u); // 先搜索子树v
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
if (low[v] > dfn[u]) { // 发现割边
|
|
|
bcnt++; // 割边数量 +1
|
|
|
bridge[v] = 1; // 因为经Tarjan算法缩点后，是一棵树，所以，bridge[v]代表的就是父节点向v的边，也就是u->v的边是割边
|
|
|
}
|
|
|
} else
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 暴力方法找到lca(a,b)
|
|
|
int lca(int a, int b) {
|
|
|
if (dfn[a] > dfn[b]) swap(a, b); // 利有dfn的物理含义，可以知道a和b的最终生成树中的深度关系
|
|
|
|
|
|
// 本题与什么缩点没有一毛钱关系，只是在讨论割边。
|
|
|
// 整体思路就是用Tarjan算法求出割边，然后尝试连接(a,b),如样例的图所示
|
|
|
// b节点，满足b在a下面就一直向上，直到不能再上，再上就跑到a上面去了为止
|
|
|
// 对于两个深度的节点a,b,先将a,b对齐到同一高度
|
|
|
while (dfn[a] < dfn[b]) {
|
|
|
if (bridge[b]) bcnt--;
|
|
|
bridge[b] = 0;
|
|
|
b = p[b];
|
|
|
}
|
|
|
// 然后再两个节点一起向上跳，这是为了照顾效率吗？
|
|
|
while (a != b) {
|
|
|
if (bridge[a]) bridge[a] = 0, bcnt--; // 如果p[a]->a是割边的话，那么现在因为有了环，将不再是割边
|
|
|
if (bridge[b]) bridge[b] = 0, bcnt--; // 如果p[b]->b是割边的话，那么现在因为有了环，将不再是割边
|
|
|
a = p[a], b = p[b]; // 一路向上
|
|
|
}
|
|
|
|
|
|
return a;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("POJ3694.in", "r", stdin);
|
|
|
#endif
|
|
|
int cas = 0;
|
|
|
while (~scanf("%d%d", &n, &m)) {
|
|
|
if (n == m && n == 0) break;
|
|
|
|
|
|
ts = bcnt = 0;
|
|
|
memset(h, -1, sizeof h); // 初始化链式前向星
|
|
|
memset(low, 0, sizeof low); // 初始化Tarjan算法需要的数组
|
|
|
memset(dfn, 0, sizeof dfn); // 初始化Tarjan算法需要的数组
|
|
|
memset(bridge, 0, sizeof bridge); // 记录某条边是不是桥
|
|
|
for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集
|
|
|
|
|
|
printf("Case %d:\n", ++cas);
|
|
|
while (m--) {
|
|
|
int a, b;
|
|
|
scanf("%d%d", &a, &b);
|
|
|
add(a, b), add(b, a);
|
|
|
}
|
|
|
|
|
|
// 因为是无向则连通的图，所以所有点必然都连通，也就是从1号点可以到达任意点，
|
|
|
// 不需要枚举每个点，并且判断dfn[i]==0进行判断
|
|
|
tarjan(1, 0);
|
|
|
|
|
|
// q次询问
|
|
|
int q;
|
|
|
scanf("%d", &q);
|
|
|
while (q--) {
|
|
|
// 添加边，如果边的两端处在不同的点上，求他们的LCA，并且减少桥的数量
|
|
|
int a, b;
|
|
|
scanf("%d%d", &a, &b);
|
|
|
lca(a, b);
|
|
|
printf("%d\n", bcnt); // 割边数量
|
|
|
}
|
|
|
puts("");
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
