考虑离线。

用Link-Cut Tree维护删除时间的最大生成树。

加入一条边时，如果两点不连通则直接link，否则肯定有一条边多余，若形成奇环则将多余的边加入集合。

删除一条边时，若这条边是树边则直接删除，否则若在集合中，则从集合中删除。

查询时，如果集合中没有边，则为二分图。

 

#include
     
      const int N=100010,M=200010,P=300010;int n,m,T,i,x,cnt;bool on[M],in[M];struct Edge{int x,y,z;}e[M];struct E{int v;E*nxt;}*ga[N],*gd[N],pool[M<<1],*cur=pool,*p;inline void adda(int x,int y){p=cur++;p->v=y;p->nxt=ga[x];ga[x]=p;}inline void addd(int x,int y){p=cur++;p->v=y;p->nxt=gd[x];gd[x]=p;}inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int f[P],son[P][2],val[P],sum[P],mn[P],from[P],tmp[P];bool rev[P];inline void swap(int&a,int&b){int c=a;a=b;b=c;}inline bool isroot(int x){return !f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}inline void rev1(int x){if(!x)return;swap(son[x][0],son[x][1]);rev[x]^=1;}inline void pb(int x){if(rev[x])rev1(son[x][0]),rev1(son[x][1]),rev[x]=0;}inline void up(int x){  mn[x]=val[x],from[x]=x,sum[x]=x>n;  if(son[x][0]){    if(mn[son[x][0]]
      
       nxt)add(p->v);    for(p=gd[i];p;p=p->nxt)del(p->v);    puts(cnt?"No":"Yes");  }  return 0;}