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:
#pragma comment(linker,"/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize(2)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;

template <typename T>

void read(T &a)
{
	T x = 0,f = 1;
	register char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	a = x * f;
}

template <typename T>

void write(T x)
{
	if (x < 0) putchar('-'),x = -x;
	if (x < 10) return (void) putchar(x + '0');
	write(x / 10);
	putchar(x % 10 + '0');
}

template <typename T>

void writeln(T x)
{
	write(x);
	putchar('\n');
}

template <typename T>

void writes(T x)
{
	write(x);
	putchar(' ');
}

template <typename T,typename... Args> 

void read(T &t,Args &... args)
{
	read(t);
	read(args...);
}

template <typename T,typename... Args>

void writes(T t,Args ... args)
{
	writes(t);
	writes(args...);
}

template <typename T,typename... Args>

void writeln(T t,Args ... args)
{
	writes(t);
	writes(args...);
	putchar('\n');
}

int n,m,t,head[N],pnt[N << 1],nxt[N << 1],E = 0;
int siz[N],dep[N],son[N],fa[N],p[N],top[N],dfn[N],rnk[N],cnt = 0;
std::vector<int> ou;
multiset<pair<int,int>,greater<pair<int,int> > > s;

int checkmax(int x,int y)
{
	return dep[x] < dep[y] ? x : y;
}

struct ST
{
	int st[N << 1][21],LOG[N << 1];
	void build()
	{
		LOG[0] = -1;
		for (int i = 1; i < ou.size(); i++)
			LOG[i] = LOG[i >> 1] + 1;
		for (int i = 1; i < ou.size(); i++)
			st[i][0] = ou[i];
		for (int j = 1; j <= 20; j++)
			for (int i = 1; i + (1 << j) - 1 < ou.size(); i++)
				st[i][j] = checkmax(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
	}
	int query(int l,int r)
	{
		int k = LOG[r - l + 1];
		return checkmax(st[l][k],st[r - (1 << k) + 1][k]);
	}
}st;

void add_edge(int u,int v)
{
	pnt[E] = v;
	nxt[E] = head[u];
	head[u] = E++;
}

void dfs1(int u,int f)
{
	dep[u] = dep[f] + 1;
	fa[u] = f;
	siz[u] = 1;
	son[u] = -1;
	for (int i = head[u]; i != -1; i = nxt[i])
	{
		int v = pnt[i];
		if (v == f) continue;
		dfs1(v,u);
		siz[u] += siz[v];
		if (son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
	}
}

void dfs2(int u,int tp)
{
	p[u] = ou.size();
	ou.push_back(u);
	top[u] = tp;
	dfn[u] = ++cnt;
	rnk[cnt] = u;
	if (son[u] == -1) return ;
	dfs2(son[u],tp);
	ou.push_back(u);
	for (int i = head[u]; i != -1; i = nxt[i])
	{
		int v = pnt[i];
		if (v == son[u] || v == fa[u]) continue;
		dfs2(v,v);
		ou.push_back(u);
	}
}

int LCA(int x,int y)
{
	if (p[x] > p[y]) swap(x,y);
	return st.query(p[x],p[y]);
}

int getdis(int x,int y)
{
	return dep[x] + dep[y] - 2 * dep[LCA(x,y)];
}

struct path
{
	int u,v;
};

path max(path x,path y)
{
	if (x.u == -1) return y;
	if (y.u == -1) return x;
	return getdis(x.u,x.v) < getdis(y.u,y.v) ? y : x;
}

path operator+(path x,path y)
{
	path res = (path) {-1,-1};
	if (x.u == -1) return y;
	if (y.u == -1) return x;
	res = max(x,y);
	res = max(res,(path) {x.u,y.v});
	res = max(res,(path) {x.v,y.u});
	res = max(res,(path) {x.u,y.u});
	res = max(res,(path) {x.v,y.v});
	// cout << x.u << ' ' << x.v << ' ' << y.u << ' ' << y.v << ' ' << res.u << ' ' << res.v << endl;
	return res;
}

struct Segment_Tree
{
	int sum[N << 2];
	void pushup(int now)
	{
		sum[now] = sum[now << 1] + sum[now << 1 | 1];
	}
	void update(int now,int l,int r,int x,int k)
	{
		if (l == r)
		{
			sum[now] += k;
			return ;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) update(now << 1,l,mid,x,k);
		if (x > mid) update(now << 1 | 1,mid + 1,r,x,k);
		pushup(now);
	}
	int query(int now,int l,int r,int ll,int rr)
	{
		if (ll <= l && rr >= r) return sum[now];
		int mid = (l + r) >> 1,ans = 0;
		if (ll <= mid) ans += query(now << 1,l,mid,ll,rr);
		if (rr > mid) ans += query(now << 1 | 1,mid + 1,r,ll,rr);
		return ans;
	}
}T;

struct Segment_Tree2
{
	int sum[N << 2],maxx[N << 2];
	path tr[N << 2];
	void pushup(int now)
	{
		maxx[now] = max(maxx[now << 1],maxx[now << 1 | 1]);
		tr[now] = tr[now << 1] + tr[now << 1 | 1];
	}
	void build(int now,int l,int r)
	{
		maxx[now] = -1;
		tr[now] = (path) {-1,-1};
		if (l == r) return ;
		int mid = (l + r) >> 1;
		build(now << 1,l,mid);
		build(now << 1 | 1,mid + 1,r);
	}
	void update(int now,int l,int r,int x,int k)
	{
		if (l == r)
		{
			sum[now] += k;
			if (sum[now]) maxx[now] = dep[rnk[l]];
			else maxx[now] = -1;
			if (sum[now]) tr[now] = (path) {rnk[l],rnk[l]};
			else tr[now] = (path) {-1,-1};
			return ;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) update(now << 1,l,mid,x,k);
		if (x > mid) update(now << 1 | 1,mid + 1,r,x,k);
		pushup(now);
		// cout << l << ' ' << r << ' ' << tr[now].u << ' ' << tr[now].v << endl;
	}
	int querymax(int now,int l,int r,int ll,int rr)
	{
		if (ll > rr) return -1;
		if (ll <= l && rr >= r) return maxx[now];
		int mid = (l + r) >> 1,ans = -1;
		if (ll <= mid) ans = max(ans,querymax(now << 1,l,mid,ll,rr));
		if (rr > mid) ans = max(ans,querymax(now << 1 | 1,mid + 1,r,ll,rr));
		return ans;
	}
	path querypath(int now,int l,int r,int ll,int rr)
	{
		if (ll > rr) return (path) {-1,-1};
		if (ll <= l && rr >= r) return tr[now];
		int mid = (l + r) >> 1;
		path ans = (path) {-1,-1};
		if (ll <= mid) ans = ans + querypath(now << 1,l,mid,ll,rr);
		if (rr > mid) ans = ans + querypath(now << 1 | 1,mid + 1,r,ll,rr);
		return ans;
	}
}T2;

int query(int x,int k)
{
	if (!k) return x;
	while (dfn[x] - dfn[top[x]] < k && top[x] != 1)
	{
		k -= dfn[x] - dfn[top[x]] + 1;
		x = fa[top[x]];
	}
	return rnk[max(dfn[x] - k,1LL)];
}

int clac(int u,int ac)
{
	path x = T2.querypath(1,1,n,dfn[ac],dfn[ac] + siz[ac] - 1);
	if (x.u == -1) return -1;
	return max(getdis(x.u,u),getdis(x.v,u));
}

int query(int d)
{
	int u = query(s.begin() -> second,d);
	int v = query(u,d);
	if (T.query(1,1,n,dfn[v],dfn[v] + siz[v] - 1) != s.size()) return 0;
	if (clac(u,v) > d) return 0;
	int qaq = T2.querymax(1,1,n,dfn[u],dfn[u] + siz[u] - 1);
	if (qaq - dep[u] > d) return 0;
	return 1;
}

signed main()
{
	// freopen("data.in","r",stdin);
	// freopen("B.out","w",stdout);
	memset(head,-1,sizeof(head));
	read(n,m);
	for (int i = 1; i < n; i++)
	{
		int u,v;
		read(u,v);
		add_edge(u,v);
		add_edge(v,u);
	}
	ou.push_back(0);
	dfs1(1,0);
	dfs2(1,1);
	st.build();
	T2.build(1,1,n);
	for (t = 1; t <= m; t++)
	{
		int opt;
		read(opt);
		if (opt == 1)
		{
			int x,y;
			read(x,y);
			int lca = LCA(x,y);
			// cout << lca << endl;
			T.update(1,1,n,dfn[x],1);
			T.update(1,1,n,dfn[y],1);
			T.update(1,1,n,dfn[lca],-1);
			T2.update(1,1,n,dfn[lca],1);
			s.insert(make_pair(dep[lca],lca));
		}
		if (opt == 2)
		{
			int x,y;
			read(x,y);
			int lca = LCA(x,y);
			T.update(1,1,n,dfn[x],-1);
			T.update(1,1,n,dfn[y],-1);
			T.update(1,1,n,dfn[lca],1);
			T2.update(1,1,n,dfn[lca],-1);
			s.erase(s.find(make_pair(dep[lca],lca)));
		}
		if (opt == 3)
		{
			int d;
			read(d);
			puts(query(d) ? "Yes" : "No");
		}
	}
	return 0;
}