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 <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 200005
#define INF 100000000
int n,m;
struct Edge
{
	int to;
	Edge *nex;
} e[N*2];
int ne;
Edge *fir[N];
void link(int u,int v)
{
	e[ne] = {v, fir[u]};
	fir[u] = e + ne++;
}
int fa[N],dep[N],siz[N],hs[N],top[N],ls[N],in[N],out[N],cnt;
void init1(int x){
	siz[x]=1;
	for (Edge *ei=fir[x];ei;ei=ei->nex)
		if (ei->to!=fa[x]){
			fa[ei->to]=x;
			dep[ei->to]=dep[x]+1;
			init1(ei->to);
			siz[x]+=siz[ei->to];
			if (siz[ei->to]>siz[hs[x]])
				hs[x]=ei->to;
		}
}
void init2(int x,int t){
	top[x]=t;
	ls[++cnt]=x;
	in[x]=cnt;
	if (hs[x]){
		init2(hs[x],t);
		for (Edge *ei=fir[x];ei;ei=ei->nex)
			if (ei->to!=fa[x] && ei->to!=hs[x])
				init2(ei->to,ei->to);
	}
	out[x]=cnt;
}
int LCA(int u,int v){
	while (top[u]!=top[v])
		if (dep[top[u]]>dep[top[v]])
			u=fa[top[u]];
		else
			v=fa[top[v]];
	return dep[u]<dep[v]?u:v;
}
int kth(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 ls[in[x]-k];
}
struct TA{
	int t[N];
	void add(int x,int c){
		for (;x<=n;x+=x&-x)
			t[x]+=c;
	}
	int query(int x){
		int r=0;
		for (;x;x-=x&-x)
			r+=t[x];
		return r;
	}
} ta;
void addta(int x,int c){
	for (;x;x=fa[top[x]]){
		ta.add(in[top[x]],c);
		ta.add(in[x]+1,-c);
	}
}
multiset<int,greater<int> > f[N],g[N];
struct SegTree{
	int mx[N*4];
	void build(int k=1,int l=1,int r=n){
		mx[k]=-INF;
		if (l==r)
			return;
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
	}
	void change(int x,int c,int k=1,int l=1,int r=n){
		if (l==r){
			mx[k]=c;
			return;
		}
		int mid=(l+r)>>1;
		if (x<=mid) change(x,c,k<<1,l,mid);
		else change(x,c,k<<1|1,mid+1,r);
		mx[k]=max(mx[k<<1],mx[k<<1|1]);
	}
	int query(int st,int en,int k,int l,int r){
		if (st<=l && r<=en)
			return mx[k];
		int mid=(l+r)>>1,res=-INF;
		if (st<=mid) res=query(st,en,k<<1,l,mid);
		if (mid<en) res=max(res,query(st,en,k<<1|1,mid+1,r));
		return res;
	}
	int query(int st,int en){
		if (st>en)
			return -INF;
		return query(st,en,1,1,n);
	}
} anc,sub;
int ex[N];
void build(){
	for (int i=1;i<=n;++i){
		g[i].insert(-INF);
		f[top[i]].insert(-INF);
	}
	for (int i=1;i<=n;++i)
		if (i!=1 && top[i]==i)
			g[fa[i]].insert(-INF);
	anc.build();
	sub.build();
}
int mxdis(int u,int v){
	int res=sub.query(in[v],out[v])-dep[v];
	for (int x=v;dep[x]>=dep[u];x=fa[x]){
		res=max(res,anc.query(max(in[top[x]],in[u]),in[fa[x]])+dep[v]);
		x=top[x];
		if (x!=1 && dep[x]-1>=dep[u]){
			int y=fa[x];
			auto p=g[y].begin();
			if (*p==*f[x].begin())
				++p;
			res=max(res,*p+dep[v]-dep[y]*2);
			res=max(res,sub.query(in[hs[y]],out[hs[y]])+dep[v]-2*dep[y]);
		}
	}
	return res;
}
void modify(int w,int old,int now){
	sub.change(in[w],now);
	int pre=*g[w].begin();
	g[w].erase(g[w].find(old));
	g[w].insert(now);
	if (pre==*g[w].begin())
		return;
	old=pre,now=*g[w].begin();
	anc.change(in[w],now-dep[w]*2);
	for (int x=w;x;x=fa[x]){
		x=top[x];
		int pre=*f[x].begin();
		f[x].erase(f[x].find(old));
		f[x].insert(now);
		if (pre==*f[x].begin())
			break;
		old=pre,now=*f[x].begin();
		if (x!=1){
			int y=fa[x];
			pre=*g[y].begin();
			g[y].erase(g[y].find(old));
			g[y].insert(now);
			if (pre==*g[y].begin())
				break;
			old=pre,now=*g[y].begin();
			anc.change(in[y],now-dep[y]*2);
		}
	}
}
void insert(int w){
	if (ex[w]++)
		return;
	modify(w,-INF,dep[w]);
}
void erase(int w){
	if (--ex[w])
		return;
	modify(w,dep[w],-INF);
}
struct Node{bool operator()(const int x, const int y)const{return dep[x] > dep[y] || (dep[x] == dep[y] && x < y);}};
multiset<int,Node> s;
int have;
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		link(u,v);
		link(v,u);
	}
	init1(1);
	init2(1,1);
	dep[0]=-1;
	build();
	while (m--){
		int op;
		scanf("%d",&op);
		if (op==3){
			int d;
			scanf("%d",&d);
			int v=kth(*s.begin(),d),u=kth(v,d);
			if (ta.query(in[u])!=have)
				printf("No\n");
			else if (mxdis(u,v)>d)
				printf("No\n");
			else
				printf("Yes\n");
		}
		else
		{
			int x,y;
			scanf("%d%d",&x,&y);
			int lca=LCA(x,y);
			if (op==1){
				have++;
				s.insert(lca);
				addta(x,1),addta(y,1),addta(lca,-1);
				insert(lca);
			}
			else{
				have--;
				s.erase(s.find(lca));
				addta(x,-1),addta(y,-1),addta(lca,1);
				erase(lca);
			}
		}
	}
}