套路题+裸题
首先肯定离线，倒过来处理，删边->加边
连边的时候，如果不连通就连，否则在这两个点的链上打个覆盖标记，查询的时候输出没被覆盖的路径条数
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;
#define rg register
#define vd void
#define sta static
#define il inline
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=30001,maxm=100001,maxq=40001;
int FA[maxn];
il int Find(int x){return x==FA[x]?x:FA[x]=Find(FA[x]);}
int ans[maxm],n,m,q;
int ch[maxn<<1][2],fa[maxn<<1],sum[maxn<<1],idx;
bool rev[maxn<<1],tag[maxn<<1],yes[maxn<<1];
int opt[maxq],qa[maxq],qb[maxq];
typedef const int& ci;
il bool isrt(ci x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
il vd upd(ci x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+yes[x];}
il vd Rev(ci x){rev[x]^=1,swap(ch[x][0],ch[x][1]);}
il vd Cover(ci x){tag[x]=1,yes[x]=0,sum[x]=0;}
il vd down(ci x){
if(!isrt(x))down(fa[x]);
if(rev[x])Rev(ch[x][0]),Rev(ch[x][1]),rev[x]=0;
if(tag[x])Cover(ch[x][0]),Cover(ch[x][1]),tag[x]=0;
}
il vd rotate(ci x){
sta int y,z,o;y=fa[x],z=fa[y],o=x==ch[y][1];
if(!isrt(y))ch[z][ch[z][1]==y]=x;fa[x]=z;
ch[y][o]=ch[x][!o];fa[ch[x][!o]]=y;
fa[y]=x;ch[x][!o]=y;
upd(y);
}
il vd splay(ci x){
down(x);sta int y,z;
for(y=fa[x],z=fa[y];!isrt(x);rotate(x),y=fa[x],z=fa[y])
if(!isrt(y))rotate(((ch[y][0]==x)^(ch[z][0]==y))?y:x);
upd(x);
}
il vd access(int x){for(rg int y=0;x;x=fa[y=x])splay(x),ch[x][1]=y,upd(x);}
il vd makert(ci x){access(x),splay(x),Rev(x);}
il vd link(ci x,ci y){makert(x),fa[x]=y;}
il vd split(ci x,ci y){makert(x),access(y),splay(y);}
il vd Link(ci x,ci y){
if(Find(x)==Find(y))split(x,y),Cover(y);
else ++idx,yes[idx]=1,sum[idx]=1,link(x,idx),link(y,idx),FA[Find(x)]=Find(y);
}
set<pair<int,int> >yyb;
main(){
n=gi(),m=gi();idx=n;
for(rg int i=1;i<=n;++i)FA[i]=i;
int x,y,c;
for(rg int i=1;i<=m;++i){
x=gi(),y=gi();if(x>y)swap(x,y);
yyb.insert(make_pair(x,y));
}
while(c=gi(),~c){
++q,opt[q]=c,qa[q]=gi(),qb[q]=gi();
if(opt[q]==0){
if(qa[q]>qb[q])swap(qa[q],qb[q]);
yyb.erase(yyb.find(make_pair(qa[q],qb[q])));
}
}
for(set<pair<int,int> >::iterator it=yyb.begin();it!=yyb.end();++it)
Link(it->first,it->second);
for(rg int i=q;i;--i)
if(opt[i]==0)Link(qa[i],qb[i]);
else split(qa[i],qb[i]),ans[++ans[0]]=sum[qb[i]];
while(ans[0])printf("%d
",ans[ans[0]--]);
return 0;
}