思路
动态图连通性的板子，可惜我不会在线算法
离线可以使用线段树分治，每个边按照存在的时间插入线段树的对应节点中，最后再dfs一下求出解即可，注意并查集按秩合并可以支持撤销操作
由于大量使用STL跑的很慢的代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <set>
#include <map>
const int MAXN = 5101;
const int MAXM = 500100;
using namespace std;
int n,timex=0,m,ans[MAXM],cnt;
struct Udsu{
int h[MAXN],fa[MAXN];
stack<int> mer,height;
int find(int x){
if(fa[x]==x)
return x;
else
return find(fa[x]);
}
bool query(int x,int y){
return find(x)==find(y);
}
void merge(int x,int y){
x=find(x);
y=find(y);
if(h[x]<=h[y]){
mer.push(x);
fa[x]=y;
if(h[x]==h[y]){
h[y]++;
height.push(1);
}
else
height.push(0);
}
else{
mer.push(y);
fa[y]=x;
height.push(0);
}
}
void undo(void){
int x=mer.top();
mer.pop();
int val=height.top();
height.pop();
h[fa[x]]-=val;
fa[x]=x;
}
void init(void){
for(int i=1;i<=n;i++)
h[i]=1,fa[i]=i;
}
}DSU;
struct edge{
int u,v;
bool operator < (const edge &b) const{
return u<b.u||(u==b.u&&v<b.v);
}
};
struct Node{
int le,u,v;//-1 add else query
bool operator < (const Node &b) const{
return le<b.le;
}
};
map<edge,int> M;
vector<Node> seg[MAXM<<2];
void add(int l,int r,int L,int R,int o,int le,int u,int v){
// printf("add l=%d r=%d L=%d R=%d o=%d\n",l,r,L,R,o);
// Sleep(700);
if(L<=l&&r<=R){
seg[o].push_back((Node){le,u,v});
return;
}
int mid=(l+r)>>1;
if(L<=mid)
add(l,mid,L,R,o<<1,le,u,v);
if(R>mid)
add(mid+1,r,L,R,o<<1|1,le,u,v);
}
void dfs(int l,int r,int o){
// printf("l=%d r=%d o=%d\n",l,r,o);
sort(seg[o].begin(),seg[o].end());
for(int i=0;i<seg[o].size();i++){
if(seg[o][i].le==-1){
DSU.merge(seg[o][i].u,seg[o][i].v);
// printf("link %d %d\n",seg[o][i].u,seg[o][i].v);
}
else{
ans[seg[o][i].le]=DSU.query(seg[o][i].u,seg[o][i].v);
// printf("query %d %d\n",seg[o][i].u,seg[o][i].v);
}
}
if(l!=r){
int mid=(l+r)>>1;
dfs(l,mid,o<<1);
dfs(mid+1,r,o<<1|1);
}
for(int i=0;i<seg[o].size();i++)
if(seg[o][i].le==-1){
// printf("undo\n");
DSU.undo();
}
}
int main(){
scanf("%d %d",&n,&m);
DSU.init();
for(int i=1;i<=m;i++){
++timex;
int opt,u,v;
scanf("%d %d %d",&opt,&u,&v);
if(u>v)
swap(u,v);
if(opt==0){
M[((edge){u,v})]=timex;
}
if(opt==1){
// printf("addtime=%d endtime=%d\n",M[((edge){u,v})],timex);
add(1,m+1,M[((edge){u,v})],timex,1,-1,u,v);
M.erase((edge){u,v});
}
if(opt==2){
add(1,m+1,timex,timex,1,++cnt,u,v);
}
}
++timex;
for(map<edge,int>::iterator it=M.begin();it!=M.end();it++){
add(1,m+1,(*it).second,m+1,1,-1,(*it).first.u,(*it).first.v);
}
dfs(1,m+1,1);
for(int i=1;i<=cnt;i++){
printf("%s\n",(ans[i])?"Y":"N");
}
return 0;
}