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:
//starusc
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1,c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=2e5+4;
int n,Q,tim,siz[N],dep[N],son[N],top[N],idx[N],dfn[N],fa[N];
vector<int>e[N];
multiset<pair<int,int> >s;
//slpf
void dfs_1(int x){
	siz[x]=1;
	for(auto v:e[x])if(v!=fa[x]){
		fa[v]=x;
		dep[v]=dep[x]+1;
		dfs_1(v);
		siz[x]+=siz[v];
		if(siz[v]>siz[son[x]])son[x]=v;
	}
}
void dfs_2(int x,int tp){
	top[x]=tp;
	idx[dfn[x]=++tim]=x;
	if(son[x])dfs_2(son[x],tp);
	for(auto v:e[x])if(v!=fa[x]&&v!=son[x])dfs_2(v,v);
}
inline int findkth(int x,int k){
	if(k>=dep[x])return 1;
	while(dep[x]-dep[top[x]]<k){
		k-=dep[x]-dep[top[x]]+1;
		x=fa[top[x]];
	}
	return idx[dfn[x]-k];
}
inline int getlca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
		else y=fa[top[y]];
	}
	return dep[x]<dep[y]?x:y;
}
struct node{
	int p1,p2,w;
	node(){}
	node(int x,int y,int v):p1(x),p2(y),w(v){}
};
inline bool upd(int &x,int v){
	if(x<v){x=v;return 1;}
	return 0;
}
inline int distan(int x,int y){
	return (!x||!y)?-1:dep[x]+dep[y]-dep[getlca(x,y)]*2;
}
inline node operator +(const node &a,const node &b){
	node ret=a.w>b.w?a:b;
	if(upd(ret.w,distan(a.p1,b.p1))){ret.p1=a.p1;ret.p2=b.p1;}
	if(upd(ret.w,distan(a.p1,b.p2))){ret.p1=a.p1;ret.p2=b.p2;}
	if(upd(ret.w,distan(a.p2,b.p1))){ret.p1=a.p2;ret.p2=b.p1;}
	if(upd(ret.w,distan(a.p2,b.p2))){ret.p1=a.p2;ret.p2=b.p2;}
	return ret;
}
namespace seg{
	#define lc (p<<1)
	#define rc (p<<1|1)
	#define mid ((l+r)>>1)
	int a[N];
	node t[N<<2];
	void build(int p,int l,int r){
		t[p].w=-1;
		if(l==r)return;
		build(lc,l,mid);build(rc,mid+1,r);
	}
	void modify(int p,int l,int r,int x,int v){
		if(l==r){
			a[x]+=v;
			if(!a[x])t[p]=node(0,0,-1);
			else t[p]=node(idx[x],idx[x],0);
			return;
		}
		if(x<=mid)modify(lc,l,mid,x,v);
		else modify(rc,mid+1,r,x,v);
		t[p]=t[lc]+t[rc];
	}
	node query(int p,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr)return t[p];
		if(qr<=mid)return query(lc,l,mid,ql,qr);
		if(mid<ql)return query(rc,mid+1,r,ql,qr);
		return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
	}
	void out(int p,int l,int r){
		cerr<<l<<" "<<r<<" "<<t[p].p1<<" "<<t[p].p2<<" t[p]\n";
		if(l==r)return;
		out(lc,l,mid);out(rc,mid+1,r);
	}
	#undef lc
	#undef rc
	#undef mid
}
namespace sz{
	int t[N];
	inline void add(int x,int v){
		for(;x<=n;x+=x&-x)t[x]+=v;
	}
	inline int ask(int x){
		int ret=0;
		for(;x;x-=x&-x)ret+=t[x];
		return ret;
	}
}
int main(){
//	freopen("1.in","r",stdin);
	n=read();Q=read();
	for(int i=1,u,v;i<n;i++){
		u=read();v=read();
		e[u].push_back(v);e[v].push_back(u);
	} 
	seg::build(1,1,n);//
	dfs_1(1);
	dfs_2(1,0);
//	for(int i=1;i<=n;i++)cerr<<dfn[i]<<" ";cerr<<"dfn\n";
//	for(int i=1;i<=n;i++)cerr<<siz[i]<<" ";cerr<<"siz\n";
	for(int op,u,v,k,lca,x;Q--;){
		op=read();
		if(op==3){
			k=read();
			x=(*s.begin()).second;
			u=findkth(x,k);
//			for(auto v:s)cerr<<v.first<<" "<<v.second<<" s\n";
//			cerr<<x<<" "<<u<<" xu\n";
			x=findkth(u,k);
			if(sz::ask(dfn[x]+siz[x]-1)-sz::ask(dfn[x]-1)!=(signed)s.size()){puts("No");continue;}
			node res=seg::query(1,1,n,dfn[x],dfn[x]+siz[x]-1);
//			cerr<<res.p1<<" "<<res.p2<<" res\n";
			if(max(distan(res.p1,u),distan(res.p2,u))>k)puts("No");
			else puts("Yes");
			continue;
		}
		u=read();v=read();
		lca=getlca(u,v);
//		cerr<<u<<" "<<v<<" "<<lca<<" lca\n";
		if(op==1){
			s.insert(make_pair(-dep[lca],lca));
			seg::modify(1,1,n,dfn[lca],1);
			sz::add(dfn[u],1);sz::add(dfn[v],1);sz::add(dfn[lca],-1);
		}
		else{
			s.erase(s.find(make_pair(-dep[lca],lca)));
			seg::modify(1,1,n,dfn[lca],-1);
			sz::add(dfn[u],-1);sz::add(dfn[v],-1);sz::add(dfn[lca],1);
		}
//		seg::out(1,1,n);cerr<<"\n";
	} 
	return (0-0);
}