Problem: You are given a tree. We will consider simple paths on it. Let's denote path between vertices a and b as (a, b). Let d-neighborhood of a path be a set of vertices of the tree located at a distance ≤ d from at least one vertex of the path (for example, 0-neighborhood of a path is a path itself). Let P be a multiset of the tree paths. Initially, it is empty. You are asked to maintain the following queries:

  * 1 u v — add path (u, v) into P (1 ≤ u, v ≤ n). 
  * 2 u v — delete path (u, v) from P (1 ≤ u, v ≤ n). Notice that (u, v) equals to (v, u). For example, if P = \{(1, 2), (1, 2)\}, than after query 2 2 1, P = \{(1, 2)\}. 
  * 3 d — if intersection of all d-neighborhoods of paths from P is not empty output "Yes", otherwise output "No" (0 ≤ d ≤ n - 1). 

Input

The first line contains two integers n and q — the number of vertices in the tree and the number of queries, accordingly (1 ≤ n ≤ 2 ⋅ 10^5, 2 ≤ q ≤ 2 ⋅ 10^5).

Each of the following n - 1 lines contains two integers x_i and y_i — indices of vertices connected by i-th edge (1 ≤ x_i, y_i ≤ n).

The following q lines contain queries in the format described in the statement.

It's guaranteed that: 

  * for a query 2 u v, path (u, v) (or (v, u)) is present in P, 
  * for a query 3 d, P ≠ ∅, 
  * there is at least one query of the third type. 

Output

For each query of the third type output answer on a new line.

Examples

Input


1 4
1 1 1
1 1 1
2 1 1
3 0


Output


Yes


Input


5 3
1 2
1 3
3 4
4 5
1 1 2
1 5 5
3 1


Output


No


Input


10 6
1 2
2 3
3 4
4 7
7 10
2 5
5 6
6 8
8 9
1 9 9
1 9 8
1 8 5
3 0
3 1
3 2


Output


No
Yes
Yes

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
const int N=2e5+500;
int n,m;
int fst[N],nxt[N<<1],to[N<<1],mm;
void ade(int u,int v){to[++mm]=v,nxt[mm]=fst[u],fst[u]=mm;}
struct BIT
{
	int a[N];
	void update(int x,int w){for(;x<=n;x+=x&-x)a[x]+=w;}
	int query(int x){int ans=0;for(;x;x-=x&-x)ans+=a[x];return ans;}
	int query(int l,int r){return query(r)-query(l-1);}
}s1;
int euler[20][N<<1],lg[N<<1],edfn[N],euler_cnt;
int dep[N],size[N],dfn[N],nid[N],dfs_cnt;
void lca_prework()
{
	for(int i=2;i<=2*n-1;i++)lg[i]=lg[i>>1]+1;
	for(int i=1;(1<<i)<=2*n-1;i++)
		for(int j=1;j+(1<<i)-1<=2*n-1;j++)
			euler[i][j]=dep[euler[i-1][j]]<dep[euler[i-1][j+(1<<(i-1))]]?euler[i-1][j]:euler[i-1][j+(1<<(i-1))];
}
int lca(int u,int v)
{
	int l=edfn[u],r=edfn[v];if(l>r)swap(l,r);
	int len=lg[r-l+1];
	return dep[euler[len][l]]<dep[euler[len][r-(1<<len)+1]]?euler[len][l]:euler[len][r-(1<<len)+1];
}
int getdis(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
pair<int,pair<int,int> >CHAIN(const int &u,const int &v){return make_pair(getdis(u,v),make_pair(u,v));}
pair<int,int>operator +(const pair<int,int>&a,const pair<int,int>&b)
{
	if(!a.first)return b;if(!b.first)return a;
	pair<int,pair<int,int> >tmp[6];
	tmp[0]=CHAIN(a.first,a.second),tmp[1]=CHAIN(a.first,b.first),tmp[2]=CHAIN(a.first,b.second);
	tmp[3]=CHAIN(a.second,b.first),tmp[4]=CHAIN(a.second,b.second),tmp[5]=CHAIN(b.first,b.second);
	return max_element(tmp,tmp+6)->second;
}
struct Seg
{
	pair<int,int>a[N<<2];
	int cnt[N];
	void update(int rot,int lt,int rt,int q)
	{
		if(lt==rt)
		{
			if(!cnt[nid[q]])a[rot]=make_pair(0,0);
			else a[rot]=make_pair(nid[lt],nid[lt]);
			return;
		}
		int mid=(lt+rt)>>1;
		if(q<=mid)update(rot<<1,lt,mid,q);
		else update(rot<<1|1,mid+1,rt,q);
		a[rot]=a[rot<<1]+a[rot<<1|1];
	}
	void update(int u,int w)
	{
		if(!cnt[u]){cnt[u]=w;update(1,1,n,dfn[u]);return;}
		cnt[u]+=w;
		if(!cnt[u])update(1,1,n,dfn[u]);
	}
	pair<int,int>query(int rot,int lt,int rt,int lq,int rq)
	{
		if(lt>=lq&&rt<=rq)return a[rot];
		int mid=(lt+rt)>>1;
		if(rq<=mid)return query(rot<<1,lt,mid,lq,rq);
		if(lq>mid)return query(rot<<1|1,mid+1,rt,lq,rq);
		return query(rot<<1,lt,mid,lq,rq)+query(rot<<1|1,mid+1,rt,lq,rq);
	}
	pair<int,int>query(int u){return query(1,1,n,dfn[u],dfn[u]+size[u]-1);}
}s2;
int fa[N][20];
void dfs(int u,int Fa)
{
	fa[u][0]=Fa;for(int i=1;(1<<i)<=n;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	dfn[u]=++dfs_cnt;nid[dfs_cnt]=u;
	euler[0][++euler_cnt]=u;edfn[u]=euler_cnt;
	dep[u]=dep[Fa]+1;size[u]=1;
	for(int i=fst[u];i;i=nxt[i])
	{
		int v=to[i];if(v==Fa)continue;
		dfs(v,u);euler[0][++euler_cnt]=u;
		size[u]+=size[v];
	}
}
int kthfa(int u,int k)
{
	for(int i=0;(1<<i)<=k;i++)
		if(k>>i&1)u=fa[u][i];
	if(!u)u=1;return u;
}
int main()
{
//	freopen("data.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),ade(u,v),ade(v,u);
	dfs(1,0);lca_prework();
	multiset<pair<int,int> >S;
	int cn=0;
	for(int i=1,opt,u,v,d;i<=m;i++)
	{
		scanf("%d",&opt);
		if(opt==1)
		{
			++cn;
			scanf("%d%d",&u,&v);
			int l=lca(u,v);
			s1.update(dfn[u],1),s1.update(dfn[v],1),s1.update(dfn[l],-1);
			s2.update(l,1);
			S.insert(make_pair(dep[l],l));
		}
		else if(opt==2)
		{
			--cn;
			scanf("%d%d",&u,&v);
			int l=lca(u,v);
			s1.update(dfn[u],-1),s1.update(dfn[v],-1),s1.update(dfn[l],1);
			s2.update(l,-1);
			S.erase(S.find(make_pair(dep[l],l)));
		}
		else
		{
			scanf("%d",&d);if(!cn){puts("No");continue;}
			int u=(--S.end())->second;
			int x=kthfa(u,d),y=kthfa(x,d);
			if(s1.query(dfn[y],dfn[y]+size[y]-1)!=cn){puts("No");continue;}
			pair<int,int>t=s2.query(y);
			if(t.first&&max(getdis(t.first,x),getdis(t.second,x))>d){puts("No");}
			else puts("Yes");
		}
	}
}