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<bits/stdc++.h>
typedef int LL;
const LL maxn=2e5+9;
#define pb push_back
#define pii std::pair<LL,LL>
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x;
}
std::vector<LL> V[maxn];
namespace Lca{
	LL tim;
	LL dep[maxn],pos[maxn<<1],inc[maxn<<1][20],lg[maxn<<1],dfn[maxn];
	void Dfs(LL u,LL f){
		dep[u]=dep[f]+1;
		dfn[u]=++tim; pos[tim]=u;
		for(LL i=0;i<V[u].size();++i){
			LL v(V[u][i]); if(v==f) continue;
			Dfs(v,u);
			pos[++tim]=u;
		}
	}
	LL Lca(LL x,LL y){
		if(x==y) return x;
		x=dfn[x]; y=dfn[y];
		if(x>y) std::swap(x,y);
		LL len(lg[y-x+1]-1);
		x=inc[x][len]; y=inc[y-(1<<len)+1][len];
		return dep[x]<dep[y]?x:y;
	}
	LL Dis(LL x,LL y){
		return dep[x]+dep[y]-(dep[Lca(x,y)]<<1);
	}
	void Init(){
		Dfs(1,0);
		for(LL i=1;i<=tim;++i) inc[i][0]=pos[i];
		for(LL i=1;i<=tim;++i) lg[i]=lg[i>>1]+1;
		for(LL i=1;i<=19;++i){
			for(LL j=1;j+(1<<i-1)<=tim;++j){
				LL x(inc[j][i-1]),y(inc[j+(1<<i-1)][i-1]);
				inc[j][i]=(dep[x]<dep[y]?x:y);
			}
		}
	}
}
LL n,tim,q;
LL dfn[maxn],pos[maxn],low[maxn],inc[maxn][19],dep[maxn];
namespace Bit{
	LL tr[maxn];
	LL Lowbit(LL x){
		return x&(-x);
	}
	void Modify(LL x,LL v){
		//printf("%d,%d\n",x,v);
		for(;x<=n;x+=Lowbit(x)) tr[x]+=v;
		//for(LL i=1;i<=n;++i) printf("%d",tr[i]); puts("");
	}
	LL Query(LL x){
		LL ret(0);
		for(;x;x-=Lowbit(x)) ret+=tr[x];
		return ret;
	}
	LL Query(LL l,LL r){
		return Query(r)-Query(l-1);
	}
}
namespace Sgt{
	LL dia[maxn<<2][2],val[maxn<<2];
	void Merge(LL *a,LL *A,LL *B){
		if(!A[0] || !B[0]){
			for(LL i=0;i<=1;++i) a[i]=(A[i]|B[i]);
			return;
		}
		LL d1(Lca::Dis(A[0],A[1])),d2(Lca::Dis(B[0],B[1]));
		LL d=std::max(d1,d2);
		if(d1>d2){
			for(LL i=0;i<=1;++i) a[i]=A[i];
		}else{
			for(LL i=0;i<=1;++i) a[i]=B[i];
		}
		for(LL i=0;i<=1;++i){
			for(LL j=0;j<=1;++j){
				LL d3(Lca::Dis(A[i],B[j]));
				if(d3>d){
					d=d3; a[0]=A[i]; a[1]=B[j];
				}
			}
		}
	}
	void Update(LL nw){
		Merge(dia[nw],dia[nw<<1],dia[nw<<1|1]);
	}
	void Modify(LL nw,LL l,LL r,LL x,LL v){
		if(l==r){
			val[nw]+=v;
			LL u(val[nw]?pos[l]:0);
			for(LL i=0;i<=1;++i) dia[nw][i]=u;
			return;
		}
		LL mid(l+r>>1);
		if(x<=mid) Modify(nw<<1,l,mid,x,v);
		else Modify(nw<<1|1,mid+1,r,x,v);
		Update(nw);
	}
	void Query(LL nw,LL l,LL r,LL lt,LL rt,LL *A){
		if(lt<=l && rt>=r){
			for(LL i=0;i<=1;++i) A[i]=dia[nw][i];
			return;
		}
		LL mid(l+r>>1);
		LL ret1[2],ret2[2];
		memset(ret1,0,sizeof(ret1)); memset(ret2,0,sizeof(ret2));
		if(lt<=mid) Query(nw<<1,l,mid,lt,rt,ret1);
		if(rt>mid) Query(nw<<1|1,mid+1,r,lt,rt,ret2);
		Merge(A,ret1,ret2);
	}
}
void Dfs(LL u,LL f){
	dfn[u]=++tim; pos[tim]=u;
	inc[u][0]=f;
	for(LL i=0;i<V[u].size();++i){
		LL v(V[u][i]); if(v==f) continue;
		dep[v]=dep[u]+1; Dfs(v,u);
	}
	low[u]=tim;
}
LL  Get(LL x,LL d){
	if(dep[x]<=d) return 1;
	for(LL i=18;i>=0;--i) if(d&(1<<i)){
		x=inc[x][i];
	}return x;
}
void Init(){
	Dfs(1,0);
	for(LL i=1;i<=18;++i){
		for(LL j=1;j<=n;++j){
			inc[j][i]=inc[inc[j][i-1]][i-1];
		}
	}
	Lca::Init();
}
std::multiset<pii> Set;
std::multiset<pii>::iterator it1;
int main(){
	n=Read(); q=Read();
	for(LL i=1;i<n;++i){
		LL x(Read()),y(Read());
		V[x].pb(y); V[y].pb(x);
	}
	Init();
	//for(LL i=1;i<=n;++i) printf("(%d,%d) ",dfn[i],low[i]);
	//puts("");
	//puts("033");
	while(q--){
		LL op(Read());
		//printf("%d\n",op);
		if(op<=2){
			LL u(Read()),v(Read()),lca(Lca::Lca(u,v));
			//printf("%d,%d:%d\n",u,v,lca);
			LL val(op==1?1:-1);
			Bit::Modify(dfn[u],val); Bit::Modify(dfn[v],val);
			//printf("%d\n",Bit::Query(10));
			//exit(0);
			Bit::Modify(dfn[lca],-val);
			Sgt::Modify(1,1,n,dfn[lca],val);
			//printf("(%d,)%d,%d:%d\n",val,dfn[u],dfn[v],dfn[lca]);
			//printf("# %d,%d\n",Bit::Query(9,10),Bit::Query(10));
			//printf("")
			if(op==1) Set.insert(pii(-dep[lca],lca));
			else{
				it1=Set.find(pii(-dep[lca],lca));
				Set.erase(it1);
			}
			continue;
		}
		LL d(Read());
		LL u(Set.begin()->second);
		//printf("# %d:",u);
		u=Get(u,d);
        LL key(Get(u,d));
		//printf("%d\n",key);
		LL N(Set.size());
		//printf("# (%d,%d)%d\n",dfn[key],low[key],Bit::Query(dfn[key],low[key]));
		if(Bit::Query(dfn[key],low[key])!=N){
			//puts("# No");
			puts("No");
			continue;
		}
		LL dia[2];
		Sgt::Query(1,1,n,dfn[key],low[key],dia);
		LL x(dia[0]),y(dia[1]);
		//printf("%d,%d\n",x,y);
		//printf("(%d,%d:%d)(%d,%d:%d)\n",u,x,Lca::Dis(u,x),u,y,Lca::Dis(u,y));
		if(!x){
			puts("Yes");
		}else{
			if(Lca::Dis(u,x)<=d && Lca::Dis(u,y)<=d){
				puts("Yes");
			}else{
				puts("No");
			}
		}
	}
	return 0;
}