树剖维护边双
首先我们看到在整个过程中图是保证连通的，于是我们并不需要LCT来维护连通性
而这些询问询问的是两个点之间关键路径的数量，也就是无论怎么走都必须走的数量，显然这就是两点之间的割边的数量
由于这里还有一些删除操作，树剖并不支持，所以我们先将所有的答案读进来，删掉所有的边
之后我们就\(Tarjan\)把边双缩出来，之后建一棵树就好了
之后我们倒着完成所有操作
对于询问操作，我们直接询问两点之间的距离就行了
对于删除操作，由于我们提前删除完了，所以我们现在需要把边恢复过来，于是我们如果要恢复\((u,v)\)这条边的话，如果\((u,v)\)在一个边双里，我们们不需要管这个操作，而如果不在那么树上\((u,v)\)两点对应边双之间就不会存在桥了，我们直接用树剖将这些边权搞成0就好了
超级长的代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#define re register
#define maxn 30005
struct node
{
int v,nxt;
}e[maxn<<3];
int head[maxn],to[maxn],top[maxn],fa[maxn],deep[maxn],sum[maxn],son[maxn];
int a[maxn],b[maxn],belong[maxn];
int opt[maxn<<1],xx[maxn<<1],yy[maxn<<1];
int l[maxn<<2],r[maxn<<2],d[maxn<<2],tag[2][maxn<<2],t[maxn<<2];
int n,m,k,Q,p,num=0;
int tot,now;
inline int read()
{
char c=getchar();
int x=0,r=1;
while(c<'0'||c>'9'){if(c=='-') r=-1;c=getchar();}
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x*r;
}
inline void add_edge(int x,int y)
{
e[++num].v=y;
e[num].nxt=head[x];
head[x]=num;
}
void dfs1(int r)
{
sum[r]=1;
int maxx=-1;
for(re int i=head[r];i;i=e[i].nxt)
if(!deep[e[i].v])
{
deep[e[i].v]=deep[r]+1;
fa[e[i].v]=r;
dfs1(e[i].v);
sum[r]+=sum[e[i].v];
if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[r]=e[i].v;
}
}
void dfs2(int r,int topf)
{
top[r]=topf;
to[r]=++k;
b[k]=r;
if(!son[r]) return;
dfs2(son[r],topf);
for(re int i=head[r];i;i=e[i].nxt)
if(deep[e[i].v]>deep[r]&&son[r]!=e[i].v) dfs2(e[i].v,e[i].v);
}
void build(int x,int y,int i)
{
l[i]=x;
r[i]=y;
tag[0][i]=tag[1][i]=-1;
if(x==y)
{
t[i]=b[x];
d[i]=1;
return;
}
int mid=x+y>>1;
build(x,mid,i<<1);
build(mid+1,y,i<<1|1);
d[i]=d[i<<1]+d[i<<1|1];
}
inline void pushdown(int i)
{
if(tag[0][i]!=-1&&tag[1][i]!=-1)
{
tag[0][i<<1]=0;
tag[0][i<<1|1]=0;
d[i<<1]=0;
d[i<<1|1]=0;
t[i<<1]=tag[1][i<<1]=tag[1][i];
t[i<<1|1]=tag[1][i<<1|1]=tag[1][i];
tag[0][i]=-1;
tag[1][i]=-1;
}
}
void change(int x,int y,int v1,int v2,int i)
{
if(x<=l[i]&&y>=r[i])
{
d[i]=v1;
t[i]=v2;
tag[0][i]=v1;
tag[1][i]=v2;
return;
}
pushdown(i);
int mid=l[i]+r[i]>>1;
if(y<=mid) change(x,y,v1,v2,i<<1);
else if(x>mid) change(x,y,v1,v2,i<<1|1);
else change(x,y,v1,v2,i<<1),change(x,y,v1,v2,i<<1|1);
d[i]=d[i<<1]+d[i<<1|1];
}
int query(int x,int y,int i)
{
if(x<=l[i]&&y>=r[i]) return d[i];
pushdown(i);
int mid=l[i]+r[i]>>1;
if(y<=mid) return query(x,y,i<<1);
if(x>mid) return query(x,y,i<<1|1);
return query(x,y,i<<1|1)+query(x,y,i<<1);
}
int ask(int x,int i)
{
if(l[i]==r[i]) return t[i];
pushdown(i);
int mid=l[i]+r[i]>>1;
if(x<=mid) return ask(x,i<<1);
return ask(x,i<<1|1);
}
inline int tree_query(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) std::swap(x,y);
ans+=query(to[top[x]],to[x],1);
x=fa[top[x]];
}
if(x==y) return ans;
if(deep[x]>deep[y]) std::swap(x,y);
ans+=query(to[x]+1,to[y],1);
return ans;
}
inline void tree_change(int x,int y,int k)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) std::swap(x,y);
change(to[top[x]],to[x],0,k,1);
x=fa[top[x]];
}
if(x==y) return;
if(deep[x]>deep[y]) std::swap(x,y);
change(to[x]+1,to[y],0,k,1);
}
namespace Tarjan
{
int dfn[maxn],low[maxn],st[maxn];
std::set< std::pair<int,int> > s;
int head[maxn];
struct EDGE
{
int v,nxt;
}e[maxn<<3],E[maxn<<3];
int num=0,cnt,mid,top;
inline void add(int x,int y)
{
e[++num].v=y;
e[num].nxt=head[x];
head[x]=num;
}
void tarjan(int x,int fa)
{
st[++top]=x;
dfn[x]=low[x]=++cnt;
for(re int i=head[x];i;i=e[i].nxt)
if(!dfn[e[i].v]) tarjan(e[i].v,x),low[x]=std::min(low[x],low[e[i].v]);
else if(e[i].v!=fa) low[x]=std::min(low[x],dfn[e[i].v]);
if(low[x]==dfn[x])
{
p++;
do
{
mid=st[top--];
belong[mid]=p;
}while(x!=mid);
}
}
void prepare()
{
n=read();
m=read();
for(re int i=1;i<=m;i++)
E[i].v=read(),E[i].nxt=read();
int x,y;
while(1)
{
opt[Q+1]=read();
if(opt[Q+1]==-1) break;
if(opt[Q+1]==1) tot++;
Q++;
xx[Q]=read();
yy[Q]=read();
if(!opt[Q])
{
s.insert(std::make_pair(xx[Q],yy[Q]));
s.insert(std::make_pair(yy[Q],xx[Q]));
}
}
for(re int i=1;i<=m;i++)
if(s.find(std::make_pair(E[i].v,E[i].nxt))==s.end()&&s.find(std::make_pair(E[i].nxt,E[i].v))==s.end())
add(E[i].v,E[i].nxt),add(E[i].nxt,E[i].v);
tarjan(1,0);
for(re int i=1;i<=n;i++)
for(re int j=head[i];j;j=e[j].nxt)
if(belong[i]!=belong[e[j].v]) add_edge(belong[i],belong[e[j].v]);
}
}
int main()
{
Tarjan::prepare();
deep[1]=1;
dfs1(1);
now=tot;
dfs2(1,1);
build(1,p,1);
change(1,1,0,b[1],1);
for(re int T=Q;T;T--)
{
if(opt[T]==1) a[now--]=tree_query(belong[xx[T]],belong[yy[T]]);
else
{
if(ask(to[belong[xx[T]]],1)==ask(to[belong[yy[T]]],1)) continue;
tree_change(belong[xx[T]],belong[yy[T]],++p);
}
}
for(re int i=1;i<=tot;i++)
printf("%d\n",a[i]);
return 0;
}