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>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n,m;
vector<int>e[maxn];

int fa[maxn][21],dep[maxn],L[maxn],R[maxn],idx,que[maxn];
void dfs(int u,int pa)
{
	fa[u][0]=pa,dep[u]=dep[pa]+1,L[u]=++idx,que[idx]=u;
	For(i,1,20)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(auto v:e[u])if(v!=pa)dfs(v,u);
	R[u]=idx;
}
inline int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	Rep(i,20,0)if(dep[fa[u][i]]>=dep[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 dist(int u,int v){
	if(!u||!v)return 0;
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
inline int getfa(int u,int d){
	d=min(d,dep[u]-1);
	Rep(i,20,0)if(d>>i&1)u=fa[u][i];
	return u;
}

int tr[maxn];
inline void add(int x,int y){
	for(;x<=n;x+=x&-x)tr[x]+=y;
}
inline int ask(int x){
	int res=0;
	for(;x;x^=x&-x)res+=tr[x];
	return res;
}
inline int ask(int l,int r){return ask(r)-ask(l-1);}

int nowcnt;
multiset<pii>st;

struct path{
	int x,y;
	path(int x=0,int y=0):x(x),y(y){}
	bool operator <(const path&b)const{
		int d1=dist(x,y),d2=dist(b.x,b.y);
		if(d1!=d2)return d1<d2;
		return (x|y)<(b.x|b.y);
	}
};
path merge(path a,path b){
	return max(max(a,b),max(max(path(a.x,b.x),path(a.x,b.y)),max(path(a.y,b.x),path(a.y,b.y))));
}

struct smt{
	int sum[maxn];
	path val[maxn<<2];
	void mdf(int p,int l,int r,int x,int o)
	{
		if(l==r){
			if(o==1)val[p]=path(que[l],que[l]);
			else val[p]=path(0,0);
			return ;
		}int mid=l+r>>1;
		x<=mid?mdf(p<<1,l,mid,x,o):mdf(p<<1|1,mid+1,r,x,o);
		val[p]=merge(val[p<<1],val[p<<1|1]);
	}
	path ask(int p,int l,int r,int ql,int qr)
	{
		if(l>=ql&&r<=qr)return val[p];
		int mid=l+r>>1;
		if(qr<=mid)return ask(p<<1,l,mid,ql,qr);
		if(ql>mid) return ask(p<<1|1,mid+1,r,ql,qr);
		return merge(ask(p<<1,l,mid,ql,qr),ask(p<<1|1,mid+1,r,ql,qr));
	}
	inline void add(int x){
		if(!sum[x])mdf(1,1,n,L[x],1);
		++sum[x];
	}
	inline void del(int x){
		--sum[x];
		if(!sum[x])mdf(1,1,n,L[x],-1);
	}
}T;

bool judge(int d)
{
	int x=(*(--st.end())).se;
	x=getfa(x,d);
	int y=getfa(x,d);
//	cout<<"x,y "<<x<<' '<<y<<endl;
	if(ask(L[y],R[y])!=nowcnt)return 0;
	path p=T.ask(1,1,n,L[y],R[y]);
//	cout<<p.x<<' '<<p.y<<endl;
	return dist(x,p.x)<=d && dist(x,p.y)<=d;
}

signed main()
{
	n=read(),m=read();
	For(i,2,n){
		int u=read(),v=read();
		e[u].pb(v),e[v].pb(u);
	}
	dfs(1,0);
	For(_,1,m){
		int o=read(),u,v,d;
		if(o==3)puts(judge(read())?"Yes":"No");
		else{
			u=read(),v=read();
			int w=lca(u,v);
			o=(o==1)?(1):(-1); nowcnt+=o;
			add(L[u],o),add(L[v],o),add(L[w],-o);
			if(o==1)st.insert(mkp(dep[w],w)),T.add(w);
			else st.erase(st.find(mkp(dep[w],w))),T.del(w);
		}
	}
	return 0;
}