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;
#define ll long long
const int maxn = 200005;
int n, q;
int last[maxn], Next[maxn << 1], to[maxn << 1], cnt;
inline void addedge(int x, int y) {
	Next[++cnt] = last[x];
	last[x] = cnt, to[cnt] = y;
}
int dfn[maxn], Id[maxn], tot, ed[maxn];
int dep[maxn], fa[maxn][18], Log[maxn];
void dfs(int x) {
	dfn[x] = ++tot, Id[tot] = x;
	dep[x] = dep[fa[x][0]] + 1;
	for(int i = 1; i <= Log[dep[x]]; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(int i = last[x]; i; i = Next[i]) {
		int v = to[i];
		if(v != fa[x][0]) {
			fa[v][0] = x;
			dfs(v);
		}
	}
	ed[x] = tot;
}
int jump(int x, int d) {
	if(dep[x] <= d) return 1;
	for(int i = Log[d]; i >= 0; i--)
		if((d >> i) & 1) x = fa[x][i];
	return x;
}
int getlca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	int l = dep[x] - dep[y];
	for(int i = Log[l]; i >= 0; i--)
		if((l >> i) & 1) x = fa[x][i];
	if(x == y) return x;
	for(int i = Log[dep[x]]; i >= 0; i--)
		if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
inline int getdis(int x, int y) { return dep[x] + dep[y] - dep[getlca(x, y)] * 2; }
multiset<pair<int, int> > s; 

int t[maxn];
inline int lowbit(int x) { return x & (-x); }
inline int ask(int x) {
	int res = 0;
	for(int i = x; i >= 1; i -= lowbit(i)) res += t[i];
	return res;
}
inline int ask(int l, int r) { return ask(r) - ask(l - 1); }
inline void update(int x, int y) {
	for(int i = x; i <= n; i += lowbit(i)) t[i] += y;
}

namespace sgt { // to maintain the diameter of virtual tree
	struct dia {
		int a[2], len;
		dia(int _x = 0, int _y = 0, int _l = 0) {  a[0] = _x, a[1] = _y, len = _l; }
		friend bool operator < (dia x, dia y) { return x.len < y.len; }
		friend dia operator + (dia x, dia y) {
			if(!x.a[0]) return y;
			if(!y.a[0]) return x;
			dia z = max(x, y);
			for(int i = 0; i <= 1; i++)
				for(int j = 0; j <= 1; j++) z = max(z, dia(x.a[i], y.a[j], getdis(x.a[i], y.a[j])));
			return z;
		} 
	};
	dia T[maxn << 2];
	int val[maxn << 2];
	inline void pushup(int id) { T[id] = T[id << 1] + T[id << 1 | 1]; }
	void modify(int l, int r, int id, int x, int y) {
		if(l == r) {
			val[id] += y;
			T[id] = (val[id]) ? dia(Id[l], Id[l], 0) : dia();
			return;
		}
		int mid = (l + r) >> 1;
		if(x <= mid) modify(l, mid, id << 1, x, y);
		else modify(mid + 1, r, id << 1 | 1, x, y);
		pushup(id);
	}
	dia query(int l, int r, int id, int L, int R) {
		if(L <= l && r <= R) return T[id];
		int mid = (l + r) >> 1;
		dia res;
		if(L <= mid) res = res + query(l, mid, id << 1, L, R);
		if(R > mid) res = res + query(mid + 1, r, id << 1 | 1, L, R);
		return res;
	}
}
using namespace sgt;

void change(int x, int y, int lca, int z) {
	update(dfn[x], z), update(dfn[y], z), update(dfn[lca], -z);
	modify(1, n, 1, dfn[lca], z);
} 
int calc(int x, int y) {
	dia res = query(1, n, 1, dfn[y], ed[y]);
	return max(getdis(res.a[0], x), getdis(res.a[1], x));
}

int main() {
	scanf("%d%d", &n, &q);
	for(int i = 1, x, y; i < n; i++) {
		scanf("%d%d", &x, &y);
		addedge(x, y), addedge(y, x);
	}
	for(int i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
	dfs(1);
	for(int i = 1, opt, x, y, d; i <= q; i++) {
		scanf("%d", &opt);
		if(opt <= 2) scanf("%d%d", &x, &y); 
		if(opt == 1) {
			int lca = getlca(x, y);
			s.insert(make_pair(dep[lca], lca));
			change(x, y, lca, 1);
		}
		if(opt == 2) {
			int lca = getlca(x, y);
			s.erase(s.find(make_pair(dep[lca], lca)));
			change(x, y, lca, -1);
		}
		if(opt == 3) {
			scanf("%d", &d);
			int u = (*s.rbegin()).second;
			x = jump(u, d), y = jump(x, d);
			if(ask(dfn[y], ed[y]) != s.size()) {
				puts("No");
				continue;
			}
			(calc(x, y) <= d) ? puts("Yes") : puts("No");
		}
	}
	return 0;
}