线段树分治。

我们发现这个形式就是线段树分治，那么我们就线段树分治。我们考虑如何在按秩合并并查集上维护二分图的关系。假设我们现在在同一个并查集中的 \(x\) 和 \(y\) 上连边，考虑它们到根的距离 \(dep_x\) 和 \(dep_y\)，如果加起来是偶数，就会产生奇环，否则不会对图的二分性产生影响。而到根的距离可以通过暴力跳父亲得到。

然后考虑合并两个并查集。我们发现了问题。我们在 \(x\) 和 \(y\) 连边，实际上是在 \(getfa_x\) 和 \(getfa_y\) 上连边。但是这样有可能 \(x\) 和 \(y\) 被涂成同颜色。本来应该是 \(x\) 和 \(y\) 涂成不同颜色，现在却是 \(getfa_x\) 和 \(getfa_y\) 涂成同一颜色。这样会出问题。

考虑给并查集上的边加上边权，\(1\) 代表“两边不同色”，\(0\) 代表“两边同色”。每次 \(merge\) 的时候，找到“如果 \(x\) 和 \(y\) 不同色，\(getfa_x\) 和 \(getfa_y\) 是否应当同色”，从而决定边权。这样，\(getfa_x\) 到 \(getfa_y\) 的边其实不是真正的边，而是两点通过 \(x\) 和 \(y\) 相连的一条总和为 \(0\) 的路径。因为异或的性质，在二分图上两者是等价的。

我们就可以每次连边的时候判断是否会产生奇环，从而进行联通。

另一种做法是对每个点 \(x\) 构建 \(x+n\)，将 \(x\) 和 \(y\) 连边其实是把 \(x\) 和 \(y+n\)，\(y\) 和 \(x+n\) 连边。如果出现了奇环，等价于出现 \(a\) 和 \(b\) 连边或 \(a+n\) 和 \(b+n\) 连边，就可以利用普通的并查集维护。

边权并查集做法：

int fa[100005],deg[100005],top,vfa[100005];
struct qry{
	int x,y,d;
	qry(){
		x=0,y=0,d=0;
	}
	qry(int _x,int _y,int _d){
		x=_x,y=_y,d=_d;
	}
}st[100005];
inline int getfa(int x){
	if(fa[x]==x)return x;
	return getfa(fa[x]);
}
inline int getdep(int x){
	if(fa[x]==x)return 0;
	return getdep(fa[x])^vfa[x];
}
inline void merge(int x,int y,int v){
	if(deg[x]<deg[y])swap(x,y);
	int cd=(deg[x]==deg[y]);
	st[++top]={x,y,cd};
	fa[y]=x,deg[x]+=cd,vfa[y]=v;
}
inline void pushout(){
	int x=st[top].x,y=st[top].y,d=st[top].d;
	top--,fa[y]=y,deg[x]-=d,vfa[y]=1;
}
struct node{
	int l,r,ans;
	vt<pii>v;	
}sg[400005];
inline void init(int i,int l,int r){
	sg[i].l=l,sg[i].r=r;sg[i].v.clear(),sg[i].ans=1;
	if(l==r)return;
	init(i<<1,l,l+r>>1);
	init(i<<1|1,(l+r>>1)+1,r);
}
inline void add(int i,int l,int r,int x,int y){
	if(sg[i].l>r||sg[i].r<l)return;
	if(sg[i].l>=l&&sg[i].r<=r){
		sg[i].v.pb({x,y});
		return;
	}
	add(i<<1,l,r,x,y);
	add(i<<1|1,l,r,x,y);
}
inline void solve(int i){
	int curcnt=0;
	for(auto j:sg[i].v){
		int x=j.first,y=j.second;
		if(getfa(x)==getfa(y)){
			if(!(getdep(x)^getdep(y))){
				sg[i].ans=0;
				rd(_,curcnt)pushout();
				return;
			}
		}else{
			curcnt++;
			merge(getfa(x),getfa(y),(getdep(x)^(getdep(y))^1));
		}
	}
	if(sg[i].l!=sg[i].r){
		solve(i<<1);
		solve(i<<1|1);
	}
	rd(_,curcnt)pushout();
}
inline void output(int i){
	if(sg[i].l==sg[i].r){
		if(sg[i].ans)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}else{
		sg[i<<1].ans&=sg[i].ans;
		sg[i<<1|1].ans&=sg[i].ans;
		output(i<<1);
		output(i<<1|1);
	}
}
int n,m,x,y;
map<pii,int>mp;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	init(1,1,m);
	rp(i,m){
		cin>>x>>y;
		if(mp.count({x,y})){
			add(1,mp[{x,y}],i-1,x,y);
			mp.erase({x,y});
		}else mp[{x,y}]=i;
	}for(auto i:mp)add(1,i.second,m,i.first.first,i.first.second);
	rp(i,n)fa[i]=i,deg[i]=1;
	solve(1);
	output(1);
	return 0;
}
//Crayan_r

扩展域并查集做法：

int a[200005],b[200005],n,m,l,r,k;
int fa[200005],deg[200005],top;
struct node{
	int u,v,w;
}stk[200005];
inline int find(int x){
	return x==fa[x]?x:find(fa[x]);
}
inline void merge(int u,int v){
	u=find(u),v=find(v);
	if(deg[u]<deg[v])swap(u,v);
	if(deg[u]==deg[v]){
		deg[u]++,stk[++top]={u,v,1},fa[v]=u;
	}else{
		fa[v]=u,stk[++top]={u,v,0};
	}
}
inline void ers(){
	int u=stk[top].u,v=stk[top].v,w=stk[top].w;
	fa[v]=v,deg[u]-=w,top--;
}
struct sgtr{
	int l,r,res;
	vt<int>ope;
}sg[800005];
inline void init(int i,int l,int r){
	sg[i].l=l,sg[i].r=r,sg[i].ope.clear();
	if(l==r)return;
	init(i<<1,l,l+r>>1);
	init(i<<1|1,(l+r>>1)+1,r);
}
inline void add(int i,int l,int r,int x){
	if(sg[i].l>r||sg[i].r<l)return;
	if(sg[i].l>=l&&sg[i].r<=r){
		sg[i].ope.pb(x);
		return;
	}
	add(i<<1,l,r,x);
	add(i<<1|1,l,r,x);
}
inline void solve(int i){
	int cnt=0;
	for(auto &x:sg[i].ope){
		int u=a[x],v=b[x];
		if(find(u)==find(v)){
			sg[i].res=1;
			break;
		}else {
			merge(u,v+n);
			merge(u+n,v);
			cnt+=2;
		}
	}
	if(sg[i].l!=sg[i].r){
		solve(i<<1);
		solve(i<<1|1);
	}
	rd(i,cnt)ers();
}
inline void qry(int i){
	if(sg[i].l==sg[i].r){
		if(sg[i].res)puts("No");
		else puts("Yes");
	}else{
		sg[i<<1].res|=sg[i].res;
		sg[i<<1|1].res|=sg[i].res;
		qry(i<<1);qry(i<<1|1);
	}
}