题意：
有n个点m条边的无向图，有环还有重边，a到b的稳定性的定义是有多少条边，单独删去会使a和b不连通。有两种操作：
1. 删去a到b的一条边
2. 询问a到b的稳定性
思路：
首先删边考虑离线，倒着做，相对于加边。先用并查集建一棵树，最精简的图，初始化树上的每条边权值为1，那么在a和b点加一条边的话，会使a到b的链上所有边因为这条新边而稳定性贡献无效，这样我们可以树链剖分，用线段树维护链上的边的稳定性贡献值。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5;
const int M = 1e5 + 5;
int n, m, q;
struct Edge {
int v, nex;
}edge[M<<2];
int head[N];
int etot;
void init_edge() {
memset (head, -1, sizeof (head));
etot = 0;
}
void add_edge(int u, int v) {
edge[etot] = (Edge) {v, head[u]};
head[u] = etot++;
}
#define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
int sum[N<<2], lazy[N<<2];
void push_up(int o) {
sum[o] = sum[o<<1] + sum[o<<1|1];
}
void push_down(int l, int r, int o) {
if (lazy[o] != -1) {
lazy[o<<1] = lazy[o];
lazy[o<<1|1] = lazy[o];
int mid = l + r >> 1;
sum[o<<1] = lazy[o] * (mid - l + 1);
sum[o<<1|1] = lazy[o] * (r - mid + 1);
lazy[o] = -1;
}
}
void build(int l, int r, int o) {
lazy[o] = -1;
if (l == r) {
sum[o] = 1;
return ;
}
int mid = l + r >> 1;
build (lson);
build (rson);
push_up (o);
}
int query(int ql, int qr, int l, int r, int o) {
if (ql <= l && r <= qr) {
return sum[o];
}
push_down (l, r, o);
int mid = l + r >> 1, ret = 0;
if (ql <= mid) ret += query (ql, qr, lson);
if (qr > mid) ret += query (ql, qr, rson);
return ret;
}
void updata(int ql, int qr, int c, int l, int r, int o) {
if (ql <= l && r <= qr) {
sum[o] = (r - l + 1) * c;
lazy[o] = c;
return ;
}
push_down (l, r, o);
int mid = l + r >> 1;
if (ql <= mid) updata (ql, qr, c, lson);
if (qr > mid) updata (ql, qr, c, rson);
push_up (o);
}
int sz[N], fa[N], dfn[N], belong[N];
int tim;
void DFS2(int u, int chain) {
dfn[u] = ++tim;
belong[u] = chain;
int k = 0;
for (int i=head[u]; ~i; i=edge[i].nex) {
Edge &e = edge[i];
if (e.v == fa[u]) continue;
if (sz[e.v] > sz[k]) k = e.v;
}
if (k) DFS2 (k, chain);
for (int i=head[u]; ~i; i=edge[i].nex) {
Edge &e = edge[i];
if (e.v == fa[u] || e.v == k) continue;
DFS2 (e.v, e.v);
}
}
void DFS(int u, int pa) {
sz[u] = 1;
fa[u] = pa;
for (int i=head[u]; ~i; i=edge[i].nex) {
Edge &e = edge[i];
if (e.v == pa) continue;
DFS (e.v, u);
sz[u] += sz[e.v];
}
}
int query_ans(int u, int v) {
int ret = 0;
int p = belong[u], q = belong[v];
while (p != q) {
if (dfn[p] < dfn[q]) {
swap (p, q);
swap (u, v);
}
ret += query (dfn[p], dfn[u], 1, n, 1);
u = fa[p];
p = belong[u];
}
if (dfn[u] < dfn[v]) swap (u, v);
if (u != v) {
ret += query (dfn[v]+1, dfn[u], 1, n, 1);
}
return ret;
}
void modify(int u, int v) {
int p = belong[u], q = belong[v];
while (p != q) {
if (dfn[p] < dfn[q]) {
swap (p, q);
swap (u, v);
}
updata (dfn[p], dfn[u], 0, 1, n, 1);
u = fa[p];
p = belong[u];
}
if (dfn[u] < dfn[v]) swap (u, v);
if (u != v) {
updata (dfn[v]+1, dfn[u], 0, 1, n, 1);
}
}
void prepare() {
sz[0] = 0;
DFS (1, 0);
tim = 0;
DFS2 (1, 1);
build (1, n, 1);
}
int rt[N];
int Find(int x) {
return rt[x] == x ? x : rt[x] = Find (rt[x]);
}
multiset<pair<int, int> > mset1, mset2;
int op[M], x[M], y[M];
int ans[M];
int main() {
int T, cas = 0;
scanf ("%d", &T);
while (T--) {
init_edge ();
scanf ("%d%d%d", &n, &m, &q);
for (int i=1; i<=n; ++i) {
rt[i] = i;
}
mset1.clear ();
for (int i=1; i<=m; ++i) {
int u, v;
scanf ("%d%d", &u, &v);
if (u > v) swap (u, v);
mset1.insert ({u, v});
}
for (int i=1; i<=q; ++i) {
scanf ("%d%d%d", &op[i], &x[i], &y[i]);
if (x[i] > y[i]) swap (x[i], y[i]);
if (op[i] == 1) mset1.erase (mset1.find ({x[i], y[i]}));
}
mset2.clear ();
for (auto &it: mset1) {
int p = Find (it.first), q = Find (it.second);
if (p == q) continue;
mset2.insert (it);
add_edge (it.first, it.second);
add_edge (it.second, it.first);
rt[p] = q;
}
prepare ();
for (auto &it: mset1) {
if (mset2.find (it) == mset2.end ()) {
modify (it.first, it.second);
}
}
for (int i=q; i>=1; --i) {
if (op[i] == 1) {
modify (x[i], y[i]);
} else {
ans[i] = query_ans (x[i], y[i]);
}
}
printf ("Case #%d:
", ++cas);
for (int i=1; i<=q; ++i) {
if (op[i] == 2) {
printf ("%d
", ans[i]);
}
}
}
return 0;
}