边双+树剖做法。

rt，这是提交记录：

https://www.luogu.com.cn/record/200220826

发现其它点的时间都很小，然而这三个点却把时间跑满了。合理怀疑是死递归、死循环。然而检查了几次都没发现问题。求调。

#include<bits/stdc++.h>
using namespace std;
//以下是快读
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x>='0'&&x<='9')
	char buf[MAXSIZE], *p1, *p2;
	char pbuf[MAXSIZE], *pp;
#if DEBUG == 1
#else
	IO():p1(buf),p2(buf),pp(pbuf){}
	~IO(){
		fwrite(pbuf,1,pp-pbuf,stdout);
	}
#endif
	bool fu;
	char gc(){
#if DEBUG == 1
		return getchar();
#endif
		if(p1==p2){
			p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin);
		}
		return p1==p2?' ':*p1++;
	}
	bool blank(char ch){
		return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
	}
	template <class T>
	void read(T &x){
		x=0;
		fu=0;
		char ch=gc();
		while(!isdigit(ch) && ch!='-'){
			ch=gc();
		}
		if(ch=='-'){
			fu=1;
			while(!isdigit(ch)){
				ch=gc();
			}
		}
		while(isdigit(ch)){
			x=(x<<3)+(x<<1)+(ch^48);
			ch=gc();
		}
		if(fu){
			x=(~x)+1;
		}
	}
	void read(char *s){
		char ch=gc();
		while(blank(ch)){
			ch=gc();
		}
		while(!blank(ch)){
			*s++=ch;
			ch=gc();
		}
		*s=0;
	}
	void read(char &ch){
		ch=gc();
		while(blank(ch)){
			ch=gc();
		}	
	}
	void push(const char &c){
#if DEBUG == 1
		putchar(c);
#else
		if(pp-pbuf==MAXSIZE){
			fwrite(pbuf,1,MAXSIZE,stdout),pp=pbuf;
		}
		*pp++=c;
#endif
	}
	template<class T>
	void write(T x){
		static T stk[256];
		T top=0;
		if(x<0){
			push('-');
			x=(~x)+1;
		}
		do{
			stk[top++]=x%10,x/=10;
		}while(x);
		while(top){
			push(stk[--top]+'0');
		}
	}
	template <class T>
	void write(T x,char lastChar){
		write(x);
		push(lastChar);
	}
}io;
//以上是快读
long long n,m,q;
unordered_multiset<long long> org[60050];
long long ask[60050][5];
stack<long long> que;
bitset<60050> inque;
long long dtot = 0,stot = 0,dfn[60050],low[60050];
long long belong[60050];
void tarjan(long long now,long long fa){
	dfn[now] = low[now] = ++dtot;
	que.push(now),inque[now] = 1;
	bool visfa = 0;
	for(auto i:org[now]){
		if(!dfn[i]){
			tarjan(i,now);
			low[now] = min(low[now],low[i]);
		}else if(inque[i]){
			if(i != fa || visfa){
				low[now] = min(low[now],dfn[i]);
			}else{
				visfa = 1;
			}
		}
	}
	if(low[now] == dfn[now]){
		long long y;
		stot++;
		do{
			y = que.top();
			que.pop();
			inque[y] = 0;
			belong[y] = stot;
		}while(y != now);
	}
	return;
}
unordered_set<long long> added;
long long etot = 0,Last[60050],Next[400050],End[400050];
void addedge(long long u,long long v){
	etot++;
	Next[etot] = Last[u];
	Last[u] = etot;
	End[etot] = v;
	return;
}
long long ntot = 0,Size[60050],fat[60050],dep[60050],Head[60050];
long long val[60050],top[60050];
void dfs1(long long now,long long fa){
	Size[now] = 1,fat[now] = 0,dep[now] = dep[fa]+1,Head[now] = fa;
	for(long long i = Last[now]; i; i = Next[i]){
		if(End[i] == fa){
			continue;
		}
		dfs1(End[i],now);
		if(fat[now] == 0 || Size[fat[now]] < Size[End[i]]){
			fat[now] = End[i];
		}
	}
	return;
}
void dfs2(long long now,long long fa){
	val[now] = ++ntot,top[now] = fa;
	if(fat[now]){
		dfs2(fat[now],fa);
	}
	for(long long i = Last[now]; i; i = Next[i]){
		if(val[End[i]]){
			continue;
		}
		dfs2(End[i],End[i]);
	}
	return;
}
long long tree[60050<<2],tag[60050<<2];
long long ls(long long x){
	return x<<1;
}
long long rs(long long x){
	return x<<1|1;
}
void push_up(long long p){
	tree[p] = tree[ls(p)]+tree[rs(p)];
	return;
}
void build(long long p,long long pl,long long pr){
	tree[p] = 0;
	tag[p] = -1;
	if(pl == pr){
		tree[p] = 1;
		return;
	}
	long long mid = pl+((pr-pl)>>1);
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
	return;
}
void addtag(long long p,long long pl,long long pr,long long opt){
	tag[p] = opt;
	tree[p] = opt*(pr-pl+1);
	return;
}
void push_down(long long p,long long pl,long long pr){
	if(~tag[p]){
		long long mid = pl+((pr-pl)>>1);
		addtag(ls(p),pl,mid,tag[p]);
		addtag(rs(p),mid+1,pr,tag[p]);
		tag[p] = -1;
	}
	return;
}
void modify(long long p,long long pl,long long pr,long long l,long long r,long long opt){
	if(l <= pl && pr <= r){
		addtag(p,pl,pr,opt);
		return;
	}
	long long mid = pl+((pr-pl)>>1);
	push_down(p,pl,pr);
	if(l <= mid){
		modify(ls(p),pl,mid,l,r,opt);
	}
	if(mid < r){
		modify(rs(p),mid+1,pr,l,r,opt);
	}
	push_up(p);
	return;
}
long long query(long long p,long long pl,long long pr,long long l,long long r){
	if(l <= pl && pr <= r){
		return tree[p];
	}
	long long mid = pl+((pr-pl)>>1),res = 0;
	push_down(p,pl,pr);
	if(l <= mid){
		res += query(ls(p),pl,mid,l,r);
	}
	if(mid < r){
		res += query(rs(p),mid+1,pr,l,r);
	}
	return res;
}
stack<long long> ans;
int main(){
	io.read(n),io.read(m);
	for(long long i = 1; i <= m; i++){
		static long long tpa,tpb;
		io.read(tpa),io.read(tpb);
		org[tpa].insert(tpb);
		org[tpb].insert(tpa);
	}
	for(q = 1; ; q++){
		static long long tpa,tpb,tpc;
		io.read(tpa);
		if(tpa == -1){
			q--;
			break;
		}
		io.read(tpb),io.read(tpc);
		ask[q][1] = tpa,ask[q][2] = tpb,ask[q][3] = tpc;
		if(tpa == 0){
			auto it = org[tpb].find(tpc);
			if(it != org[tpb].end()){
				org[tpb].erase(it);
			}
			it = org[tpc].find(tpb);
			if(it != org[tpc].end()){
				org[tpc].erase(it);
			}
		}
	}
	tarjan(1,0);
	for(long long i = 1; i <= n; i++){
		for(auto j:org[i]){
			if(belong[i] != belong[j] && added.count(belong[i]*100050+belong[j]) == 0){
				addedge(belong[i],belong[j]);
				added.insert(belong[i]*100050+belong[j]);
			}
		}
	}
	dfs1(belong[1],0);
	dfs2(belong[1],belong[1]);
	build(1,1,ntot);
	while(q--){
		static long long tpa,tpb,tpc,tpd;
		tpa = ask[q+1][1];
		tpb = ask[q+1][2];
		tpc = ask[q+1][3];
		tpb = belong[tpb],tpc = belong[tpc];
		tpd = 0;
		if(tpa == 1){
			while(top[tpb] != top[tpc]){
				if(dep[top[tpb]] < dep[top[tpc]]){
					swap(tpb,tpc);
				}
				tpd += query(1,1,ntot,val[top[tpb]],val[tpb]);
				tpb = top[tpb];
				tpb = Head[tpb];
			}
			if(dep[tpb] < dep[tpc]){
				swap(tpb,tpc);
			}
			if(tpb != tpc){
				tpd += query(1,1,ntot,val[tpc]+1,val[tpb]);
			}
			ans.push(tpd);
		}else{
			while(top[tpb] != top[tpc]){
				if(dep[top[tpb]] < dep[top[tpc]]){
					swap(tpb,tpc);
				}
				modify(1,1,ntot,val[top[tpb]],val[tpb],0);
				tpb = top[tpb];
				tpb = Head[tpb];
			}
			if(dep[tpb] < dep[tpc]){
				swap(tpb,tpc);
			}
			if(tpb != tpc){
				modify(1,1,ntot,val[tpc]+1,val[tpb],0);
			}
		}
	}
	while(ans.size()){
		io.write(ans.top(),'\n');
		ans.pop();
	}
	return 0;
}