线段树分治。
我们发现这个形式就是线段树分治，那么我们就线段树分治。我们考虑如何在按秩合并并查集上维护二分图的关系。假设我们现在在同一个并查集中的 \(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);
}
}