#include<bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
typedef long long ll;
const int mxn=3e4+10;
int n,m;
struct ed{
	int x,y;
}E[100010];
vector<int> e[mxn];
int ffa[mxn],son[mxn],dep[mxn],sz[mxn];
void dfs1(int x,int xfa){
	dep[x]=dep[xfa]+1;
	ffa[x]=xfa;
	son[x]=-1;
	sz[x]=1;
	for(int y:e[x])if(y!=xfa){
		dfs1(y,x);
		sz[x]+=sz[y];
		if(son[x]==-1||sz[y]>sz[son[x]])son[x]=y;
	}
}
int dfn[mxn],_dfn[mxn],tsp,top[mxn];
void dfs2(int x,int tp){
	dfn[x]=++tsp;
	_dfn[tsp]=x;
	top[x]=tp;
	if(~son[x]){
		dfs2(son[x],tp);
		for(int y:e[x])if(y!=ffa[x]&&y!=son[x]){
			dfs2(y,y);
		}
	}
}
struct TR{
	int c[mxn<<2],la[mxn<<2];
	void pushup(int p){
		c[p]=c[lc(p)]+c[rc(p)];
	}
	void pushdown(int p){
		if(la[p]){
			c[lc(p)]=c[rc(p)]=0;
			la[lc(p)]=la[rc(p)]=1;
			la[p]=0;
		}
	}
	void bt(int p,int l,int r){
		la[p]=0;
		if(l==r){
			c[p]=1;
			return ;
		}
		int mid=(l+r)>>1;
		bt(lc(p),l,mid);
		bt(rc(p),mid+1,r);
		pushup(p);
	}
	void change(int p,int l,int r,int x,int y){
		if(!c[p])return ;
		if(l>=x&&r<=y){
			c[p]=0;
			la[p]=1;
			return ;
		}
		pushdown(p);
		int mid=(l+r)>>1;
		if(x<=mid)change(lc(p),l,mid,x,y);
		if(y>mid)change(rc(p),mid+1,r,x,y);
		pushup(p); 
	}
	int find(int p,int l,int r,int x,int y){
		if(c[p]==0)return 0;
		if(l>=x&&r<=y)return c[p];
		pushdown(p);
		int mid=(l+r)>>1,ans=0;
		if(x<=mid)ans+=find(lc(p),l,mid,x,y);
		if(y>mid)ans+=find(rc(p),mid+1,r,x,y);
		return ans;
	}
}tr;
void change(int x,int y){
	for(;top[x]!=top[y];x=ffa[top[x]]){
		if(dep[top[x]]<dep[top[y]])x^=y^=x^=y;
		tr.change(1,1,n,dfn[top[x]],dfn[x]); 
	}
	if(dfn[x]>dfn[y])x^=y^=x^=y;
	if(dfn[x]<dfn[y])tr.change(1,1,n,dfn[x]+1,dfn[y]); 
}
int find(int x,int y){
	int ans=0; 
	for(;top[x]!=top[y];x=ffa[top[x]]){
		if(dep[top[x]]<dep[top[y]])x^=y^=x^=y;
		ans+=tr.find(1,1,n,dfn[top[x]],dfn[x]); 
	}
	if(dfn[x]>dfn[y])x^=y^=x^=y;
	if(dfn[x]<dfn[y])ans+=tr.find(1,1,n,dfn[x]+1,dfn[y]); 
	return ans;
}
int fa[mxn];
int findfa(int x){
	return fa[x]=(fa[x]==x?x:findfa(fa[x]));
}
unordered_map<int,unordered_map<int,int>> mp;
struct Q{
	int op,x,y;
}q[40010];
int qi;
vector<int> ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>E[i].x>>E[i].y;
	}
	int op;
	while(cin>>op&&(op!=-1)){
		int x,y;
		cin>>x>>y;
		q[++qi]={op,x,y};
		if(!op)mp[x][y]=mp[y][x]=1;
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		if(mp[E[i].x][E[i].y])continue;
		if(findfa(E[i].x)!=findfa(E[i].y)){
			fa[findfa(E[i].x)]=findfa(E[i].y);
			e[E[i].x].push_back(E[i].y);
			e[E[i].y].push_back(E[i].x); 
			mp[E[i].x][E[i].y]=1;
		}
	}
	dfs1(1,0);
	dfs2(1,1);
	tr.bt(1,1,n);
	for(int i=1;i<=m;i++){
		if(mp[E[i].x][E[i].y])continue;
		change(E[i].x,E[i].y);
	}
	for(int i=qi;i;i--){
		if(q[i].op){
			ans.push_back(find(q[i].x,q[i].y));
		}
		else{
			change(q[i].x,q[i].y);
		}
	}
	reverse(ans.begin(),ans.end());
	for(int i:ans){
		cout<<i<<'\n';
	}
	return 0;
}

手搓的第二道紫：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]
#define fa(p) tr[p].f
#define PII pair<int,int>
#define fi first
#define se second
map<PII,int>mp;
struct node{int ch[2],f,s,v,tag,tag1;}tr[N];int n,m;
bool notrt(int p){return (lc(fa(p))==p)||(rc(fa(p))==p);}
void pushup(int p){tr[p].s=tr[lc(p)].s+tr[rc(p)].s+tr[p].v;}
void pushdown(int p)
{
	if(tr[p].tag1)
	{
		tr[lc(p)].v=tr[lc(p)].s=0;
		tr[rc(p)].v=tr[rc(p)].s=0;
		tr[lc(p)].tag1=tr[rc(p)].tag1=1;
		tr[p].tag1=0;
	}
	if(tr[p].tag)
	{
		swap(lc(p),rc(p));
		tr[lc(p)].tag^=1;tr[rc(p)].tag^=1;
		tr[p].tag=0;
	}
}
void pushall(int p)
{
	if(notrt(p))pushall(fa(p));
	pushdown(p);
}
void rotate(int x)
{
	int y=fa(x),z=fa(y),k=rc(y)==x;
	if(notrt(y))tr[z].ch[rc(z)==y]=x;fa(x)=z;
	tr[y].ch[k]=tr[x].ch[k^1];fa(tr[x].ch[k^1])=y;
	tr[x].ch[k^1]=y;fa(y)=x;
	pushup(y);pushup(x);
}
void splay(int x)
{
	pushall(x);
	while(notrt(x))
	{
		int y=fa(x),z=fa(y);
		if(notrt(y))((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
		rotate(x);
	}
}
void access(int x)
{
	for(int y=0;x;)
	{
		splay(x);
		rc(x)=y;
		pushup(x);
		y=x;x=fa(x);
	}
}
void makert(int x)
{
	access(x);
	splay(x);
	tr[x].tag^=1;
}
void split(int x,int y)
{
	makert(x);
	access(y);
	splay(y);
}
int findrt(int x)
{
	access(x);
	splay(x);
	while(lc(x))pushdown(x),x=lc(x);
	splay(x);
	return x;
}
void link(int x,int y)
{
	makert(x);
	if(findrt(y)!=x)
		fa(x)=y;
}
void cut(int x,int y)
{
	makert(x);
	if(findrt(y)==x&&fa(y)==x&&!lc(y))
		fa(y)=0,pushup(x);
}
struct node1{int x,y,tag;}e[N],q[N];
signed main()
{
	cin>>n>>m;int qlen=0;
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].x>>e[i].y;
		e[i].tag=1;
		mp[{e[i].x,e[i].y}]=mp[{e[i].y,e[i].x}]=i;
	}
	for(int i=n+1;i<=n+m;i++)tr[i].v=1;
	for(int op,x,y;;)
	{
		cin>>op;if(op==-1)break;
		cin>>x>>y;
		q[++qlen]={x,y,op};
		if(op==0)
			e[mp[{x,y}]].tag=0;
	}
	for(int i=1;i<=m;i++)if(e[i].tag)
	{
		int x=e[i].x,y=e[i].y,id=mp[{x,y}]+n;
		split(x,y);makert(x);
		if(findrt(y)==x)
		{
			split(x,y);
			tr[y].v=tr[y].s=0;
			tr[y].tag1=1;
		}
		else
		{
			link(x,id);
			link(y,id);
		}
	}
	deque<int>ans;
	for(int i=qlen;i;i--)
	{
		int op=q[i].tag,x=q[i].x,y=q[i].y;
		if(op==1)
		{
			split(x,y);
			ans.push_front(tr[y].s);
		}
		else 
		{
			int num=mp[{x,y}],id=num+n;e[num].tag=1;
			makert(x);
			if(findrt(y)==x)
			{
				split(x,y);
				tr[y].v=tr[y].s=0;
				tr[y].tag1=1;
			}
			else
			{
				link(x,id);
				link(y,id);
			}
		}
	}
	for(int y:ans)cout<<y<<'\n';
	return 0;
}