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:
//W4P3R
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register int
#define fr first
#define sd second
#define pa pair<int,int>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define N 200010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
inline int lowbit(int x){return x&(-x);}
int n,q;
vector<int>e[N];int fa[N][21],deep[N];
int L[N],R[N],Time,nowm,Q[N];
multiset<pa>S;	
struct path{int x,y;};

inline int LCA(int u,int v)
{
	if(deep[u]<deep[v])swap(u,v);
	REP(i,20,0)if(deep[fa[u][i]]>=deep[v])u=fa[u][i];
	if(u==v)return u;
	REP(i,20,0)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
inline int dis(int x,int y)
{
	if(x<0||y<0)return -inf;
	return deep[x]+deep[y]-2*deep[LCA(x,y)];
}
path operator +(path a,path b)
{
	int x=-1,y=-1,d=-inf;
	if(dis(a.x,a.y)>d)d=dis(a.x,a.y),x=a.x,y=a.y;
	if(dis(a.x,b.x)>d)d=dis(a.x,b.x),x=a.x,y=b.x;
	if(dis(a.x,b.y)>d)d=dis(a.x,b.y),x=a.x,y=b.y;
	if(dis(a.y,b.x)>d)d=dis(a.y,b.x),x=a.y,y=b.x;
	if(dis(a.y,b.y)>d)d=dis(a.y,b.y),x=a.y,y=b.y;
	if(dis(b.x,b.y)>d)d=dis(b.x,b.y),x=b.x,y=b.y;
	return (path){x,y};
}
void dfs(int x,int father)
{
	fa[x][0]=father;FOR(i,1,20)fa[x][i]=fa[fa[x][i-1]][i-1];
	deep[x]=deep[father]+1;L[x]=++Time;Q[Time]=x;
	for(int y:e[x])if(y!=father)dfs(y,x);R[x]=Time;
}
namespace S1
{
	int c[N];
	inline void add(int x,int v){for(;x<=n;x+=lowbit(x))c[x]+=v;}
	inline int qry(int x){int s=0;for(;x;x-=lowbit(x))s+=c[x];return s;}
	inline int qry(int l,int r){return qry(r)-qry(l-1);}
}
namespace S2
{
	#define ls (x<<1)
	#define rs (x<<1|1)
	#define mid ((l+r)>>1)
	int sum[N];path t[N<<2];
	void build(int l,int r,int x)
	{
		t[x]=(path){-1,-1};if(l==r)return ;
		build(l,mid,ls);build(mid+1,r,rs);
	}
	void upd(int l,int r,int x,int pos,int opt)
	{
		if(l==r)
		{
			if(opt==+1){t[x]=(path){Q[l],Q[l]};}
			if(opt==-1){t[x]=(path){-1,-1};}
			return ;
		}
		if(pos<=mid)upd(l,mid,ls,pos,opt);
		else upd(mid+1,r,rs,pos,opt);
		t[x]=t[ls]+t[rs];
	}
	path qry(int l,int r,int x,int left,int right)
	{
		if(l==left&&right==r)return t[x];
		if(right<=mid)return qry(l,mid,ls,left,right);
		else if(left>mid)return qry(mid+1,r,rs,left,right);
		else return qry(l,mid,ls,left,mid)+qry(mid+1,r,rs,mid+1,right);
	}
	inline void add(int x)
	{
		if(!sum[x])upd(1,n,1,L[x],+1);
		sum[x]++;
	}
	inline void del(int x)
	{
		sum[x]--;
		if(!sum[x])upd(1,n,1,L[x],-1);
	}
}
inline int FA(int x,int d)
{
	if(deep[x]<=d)return 1;
	REP(i,20,0)if((1<<i)<=d){d-=(1<<i),x=fa[x][i];}
	return x;
}
inline int ask(int d)
{
	int v=(*(--S.end())).sd;v=FA(v,d);int t=FA(v,d);
	if(S1::qry(L[t],R[t])!=nowm)return 0;
	path p=S2::qry(1,n,1,L[t],R[t]);
	if(dis(v,p.x)<=d&&dis(v,p.y)<=d)return 1;
	else return 0;
}
int main()
{
	//ios::sync_with_stdio(false);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),q=read();
	FOR(i,1,n-1)
	{
		int x=read(),y=read();
		e[x].pb(y),e[y].pb(x);
	}
	dfs(1,0);S2::build(1,n,1);
	while(q--)
	{
		int opt=read();
		if(opt==1)
		{
			int u=read(),v=read();int z=LCA(u,v);
			S1::add(L[u],1);S1::add(L[v],1);S1::add(L[z],-1);
			S2::add(z);nowm++;
			S.insert(mp(deep[z],z));
		}
		if(opt==2)
		{
			int u=read(),v=read();int z=LCA(u,v);
			S1::add(L[u],-1);S1::add(L[v],-1);S1::add(L[z],1);
			S2::del(z);nowm--;
			S.erase(S.lower_bound(mp(deep[z],z)));
		}
		if(opt==3)
		{
			int d=read();
			ask(d)?cout<<"Yes\n":cout<<"No\n";
		}
	}
	return 0;
}
//gl