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>
using namespace std;
int n,q,head[200010],o=0,fa[20][200010],sz[200010],dep[200010],dfn[200010],x=0,lg2[200010],tr[200010],tot=0;
int cnt[200010];
multiset<pair<int,int> >s;
struct edge{
	int to,link;
}e[400010];
void add_edge(int u,int v){
	e[++o].to=v,e[o].link=head[u],head[u]=o;
	e[++o].to=u,e[o].link=head[v],head[v]=o;
}
void dfs(int u,int pre){
	fa[0][u]=pre,sz[u]++,dfn[u]=++x,dep[u]=dep[pre]+1;
	for(int i=head[u];i;i=e[i].link){
		if(e[i].to==pre) continue;
		dfs(e[i].to,u);
		sz[u]+=sz[e[i].to];
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int j=lg2[n];j>=0;j--) if(((dep[u]-dep[v])>>j)&1) u=fa[j][u];
	if(u==v) return u;
	for(int j=lg2[n];j>=0;j--) if(fa[j][u]!=fa[j][v]) u=fa[j][u],v=fa[j][v];
	return fa[0][u];
} 
int gfa(int u,int k){
	for(int j=lg2[n];j>=0;j--) if((k>>j)&1) u=fa[j][u];
	return u;
}
int dis(int u,int v){
	if(u<0||v<0) return INT_MIN;
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void add(int x,int w){
	for(int i=x;i<=n;i+=(i&-i)) tr[i]+=w;
}
int query(int x){
	int res=0;
	for(int i=x;i>=1;i-=(i&-i)) res+=tr[i];
	return res;
}
struct road{
	int u[2],w;
	road operator +(const road &b)const{
		road tmp=w>b.w?*this:b;
		for(int i=0;i<2;i++) for(int j=0;j<2;j++){
			if(tmp.w<dis(u[i],b.u[j])) tmp.w=dis(u[i],b.u[j]),tmp.u[0]=u[i],tmp.u[1]=b.u[j];
		}
		return tmp;
	}
}tree[800010];
void add(int a,int l,int r,int t,int w){
	if(l==r) return tree[t]=(road){{w,w},dis(w,w)},void();
	int mid=(l+r)>>1;
	if(a<=mid) add(a,l,mid,t<<1,w);
	else add(a,mid+1,r,t<<1|1,w);
	tree[t]=tree[t<<1]+tree[t<<1|1];
}
road query(int ll,int rr,int l,int r,int t){
	if(ll<=l&&r<=rr) return tree[t];
	int mid=(l+r)>>1;
	if(rr<=mid) return query(ll,rr,l,mid,t<<1);
	if(mid<ll) return query(ll,rr,mid+1,r,t<<1|1);
	return query(ll,rr,l,mid,t<<1)+query(ll,rr,mid+1,r,t<<1|1); 
} 
void add(int u,int v,int w){
	int L=lca(u,v);
	add(dfn[u],w),add(dfn[v],w);
	add(dfn[L],-w),tot+=w;
	cnt[L]+=w;
	if(!cnt[L]) add(dfn[L],1,n,1,-1);
	else if(w>0&&cnt[L]==1) add(dfn[L],1,n,1,L);
	if(w>0) s.insert(make_pair(dep[L],L));
	else s.erase(s.find(make_pair(dep[L],L)));
}
bool can(int d){
	int u=gfa((*s.rbegin()).second,d);
	int tmp=gfa(u,d);
	if(query(dfn[tmp]+sz[tmp]-1)-query(dfn[tmp]-1)!=tot) return false;
	road sth=query(dfn[tmp],dfn[tmp]+sz[tmp]-1,1,n,1);
	if(dis(u,sth.u[0])>d||dis(u,sth.u[1])>d) return false;
	return true;
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),add_edge(u,v);
	dfs(1,1);
	for(int j=1;j<=lg2[n];j++) for(int i=1;i<=n;i++) fa[j][i]=fa[j-1][fa[j-1][i]];
	for(int i=1;i<=n;i++) add(i,1,n,1,-1);
	while(q--){
		int op,x,y;
		scanf("%d%d",&op,&x);
		if(op==3){
			puts(can(x)?"Yes":"No");
			continue;
		}
		scanf("%d",&y);
		if(op==1) add(x,y,1);
		else add(x,y,-1);
	}
}