#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define mkp make_pair

#define ls c[x][0]

#define rs c[x][1]

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=1e4+,M=5e5+;

int n,m,tot,op[M],fa[N],c[N][],sta[N],top;

int del_pl[N],del_top;

bool rev[N];

map<pair<int,int>,int> mp;

struct Node{int x,y,t;}a[M];

struct Dt{

  int t,id,bh;

  Dt(int a=,int b=,int c=):t(a),id(b),bh(c) {}

}vl[N],mn[N];

Dt Mn(Dt x,Dt y)

{

  if(!x.t)return y; if(!y.t)return x;

  return (x.t<y.t)?x:y;

}

int New()

{

  int ret=(del_top?del_pl[del_top--]:++tot);

  c[ret][]=c[ret][]=fa[ret]=; return ret;

}

bool isroot(int x){return c[fa[x]][]!=x&&c[fa[x]][]!=x;}

void pshp(int x){mn[x]=Mn(vl[x],Mn(mn[ls],mn[rs]));}

void Rev(int x)

{

  if(!rev[x])return; rev[x]=;

  rev[ls]^=; rev[rs]^=; swap(ls,rs);

}

void rotate(int x)

{

  int y=fa[x],z=fa[y],d=(x==c[y][]);

  if(!isroot(y))c[z][y==c[z][]]=x;

  fa[x]=z;

  fa[y]=x; fa[c[x][!d]]=y;

  c[y][d]=c[x][!d]; c[x][!d]=y;

  pshp(y); pshp(x);

}

void splay(int x)

{

  sta[top=]=x;

  for(int k=x;!isroot(k);k=fa[k])sta[++top]=fa[k];

  for(int i=top;i;i--)Rev(sta[i]);

  while(!isroot(x))

    {

      int y=fa[x],z=fa[y];

      if(!isroot(y))

    ((x==c[y][])^(y==c[z][]))?rotate(x):rotate(y);

      rotate(x);

    }

}

void access(int x)

{

  for(int t=;x;rs=t,pshp(x),t=x,x=fa[x])splay(x);

}

void mkrt(int x)

{

  access(x);splay(x);rev[x]^=;

}

void link(int x,int y)

{

  mkrt(x); fa[x]=y;

}

void cut(int x,int y)

{

  mkrt(x); access(y); splay(y);

  c[y][]=; pshp(y); fa[x]=;

}

bool chk(int x,int y)

{

  mkrt(x); access(y); splay(y);

  while(c[y][])y=c[y][];

  return x==y;

}

void ins(Node cr,int id)

{

  int x=cr.x,y=cr.y;

  if(chk(x,y))

    {

      splay(x);

      Dt tp=mn[x]; if(tp.t>cr.t)return;

      Node k=a[tp.id]; int bh=tp.bh;

      cut(k.x,bh); cut(k.y,bh); del_pl[++del_top]=bh;

    }

  int nw=New(); mn[nw]=vl[nw]=Dt(cr.t,id,nw);

  link(cr.x,nw); link(cr.y,nw);

}

int qry(int x,int y)

{

  if(!chk(x,y))return ;

  splay(x); return mn[x].t;

}

int main()

{

  n=rdn();m=rdn();

  for(int i=;i<=n;i++)mn[i]=vl[i]=Dt(,,); tot=n;

  for(int i=;i<=m;i++)

    {

      op[i]=rdn();int x=rdn(),y=rdn();if(x>y)swap(x,y);//

      if(op[i]==)mp[mkp(x,y)]=i,a[i].x=x,a[i].y=y,a[i].t=m+;//m+1

      else if(op[i]==)a[mp[mkp(x,y)]].t=i;

      else a[i].x=x,a[i].y=y;

    }

  for(int i=;i<=m;i++)

    {

      if(op[i]==)ins(a[i],i);

      if(op[i]==)puts(qry(a[i].x,a[i].y)>i?"Y":"N");

    }

  return ;

}

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#define ls Ls[cr]

#define rs Rs[cr]

#define pb push_back

#define mkp make_pair

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=,M=5e5+,K=;

int n,m,op[M],fa[N],siz[N],top; bool vis[M],ans[M];

int tot,Ls[M<<],Rs[M<<],sm[M<<];

struct Node{

  int x,y;

  Node(int x=,int y=):x(x),y(y) {}

}a[M],sta[N];

vector<Node> vt[M<<];

map<pair<int,int>,int> mp;

void build(int l,int r,int cr)

{

  if(l==r)return; int mid=l+r>>;

  ls=++tot; build(l,mid,ls);

  rs=++tot; build(mid+,r,rs);

}

void ins(int l,int r,int cr,int L,int R,Node k)

{

  if(l>=L&&r<=R){vt[cr].pb(k);return;}

  int mid=l+r>>;

  if(L<=mid)ins(l,mid,ls,L,R,k);

  if(mid<R)ins(mid+,r,rs,L,R,k);

}

void cz(int l,int r,int cr)

{

  if(l==r){sm[cr]=(op[l]==?:);return;}

  int mid=l+r>>;

  cz(l,mid,ls); cz(mid+,r,rs);

  sm[cr]=sm[ls]+sm[rs];

}

int fnd(int a){return fa[a]==a?a:fnd(fa[a]);}

void mrg(Node a)

{

  int x=fnd(a.x),y=fnd(a.y);

  if(x==y)return; if(siz[x]<siz[y])swap(x,y);

  sta[++top]=Node(y,x); fa[y]=x; siz[x]+=siz[y];

}

void solve(int l,int r,int cr)

{

  int sz=vt[cr].size();

  for(int i=;i<sz;i++)mrg(vt[cr][i]);

  if(l==r)

    {ans[l]=(fnd(a[l].x)==fnd(a[l].y));return;}

  int mid=l+r>>;

  if(sm[ls])

    {

      int nw=top; solve(l,mid,ls);

      for(int& i=top;i>nw;i--)

    {

      int x=sta[i].x,y=sta[i].y;

      fa[x]=x; siz[y]-=siz[x];

    }

    }

  if(sm[rs])

    {

      int nw=top; solve(mid+,r,rs);

      for(int& i=top;i>nw;i--)

    {

      int x=sta[i].x,y=sta[i].y;

      fa[x]=x; siz[y]-=siz[x];

    }

    }

}

int main()

{

  n=rdn();m=rdn();

  tot=;build(,m,);

  for(int i=;i<=m;i++)

    {

      op[i]=rdn();int x=rdn(),y=rdn();

      if(x>y)swap(x,y);//

      if(!op[i])

    {

      a[i]=Node(x,y);

      mp[mkp(x,y)]=i;

    }

      else if(op[i]==)

    {

      int bh=mp[mkp(x,y)]; vis[bh]=;

      ins(,m,,bh,i-,a[bh]);

    }

      else a[i]=Node(x,y);

    }

  for(int i=;i<=m;i++)

    if(!op[i]&&!vis[i])ins(,m,,i,m,a[i]);

  cz(,m,); for(int i=;i<=n;i++)fa[i]=i,siz[i]=;

  solve(,m,);

  for(int i=;i<=m;i++)

    if(op[i]==)puts(ans[i]?"Y":"N");

  return ;

}