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:
// Mivik 2021.4.7
#include <cassert>
#include <cctype>
#include <climits>
#include <cstdio>
#include <vector>

#define ls (x << 1)
#define rs (ls | 1)
#define G const int mid = (l + r) >> 1
#define LL ls, l, mid
#define RR rs, mid + 1, r

#define R (read<int>())

char ib[1 << 20], *is, *ie, ob[1 << 15], *op = ob;
inline char gc() { if (is == ie) ie = (is = ib) + fread(ib, 1, sizeof(ib), stdin); return *is++; }
inline char rc() { char c; while (isspace(c = gc())) {} return c; }
template<class T>
inline T read() {
	T r = 0; int c; while ((c = gc()) < 48);
	while (c >= 48) { r = r * 10 + (c ^ 48); c = gc(); }
	return r;
}
inline void flush() { fwrite(ob, 1, op - ob, stdout); op = ob; }
inline void pc(char c) { *op++ = c; if (op == ob + sizeof(ob)) flush(); }
inline void nl() { pc('\n'); }
struct flush_at_exit { ~flush_at_exit() { flush(); } } flush_helper;

const int $n = 200005;
const int $t = 524290;

template<typename T> inline bool gmin(T& a, const T& b) { return b < a && (a = b, true); }
template<typename T> inline bool gmax(T& a, const T& b) { return a < b && (a = b, true); }

int n, m, dep[$n], siz[$n], son[$n], top[$n], fa[$n], dfn[$n], seq[$n], cnt[$n];
std::vector<int> outs[$n];
void dfs(int x) {
	siz[x] = 1;
	dep[x] = dep[fa[x]] + 1;
	for (int v : outs[x]) {
		if (v == fa[x]) continue;
		fa[v] = x; dfs(v);
		siz[x] += siz[v];
		if (siz[v] > siz[son[x]]) son[x] = v;
	}
}
void load(int x, int t) {
	static int dt; seq[dfn[x] = ++dt] = x;
	top[x] = t; if (son[x]) load(son[x], t);
	for (int v : outs[x]) if (v != fa[x] && v != son[x]) load(v, v);
}
inline bool contains(int x, int y) { return dfn[x] <= dfn[y] && dfn[y] < dfn[x] + siz[x]; }
inline int lca(int x, int y) {
	if (contains(x, y)) return x;
	if (contains(y, x)) return y;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y]? x: y;
}
inline int dist(int x, int y) { return dep[x] + dep[y] - dep[lca(x, y)] * 2; }
inline int kth(int x, int k) {
	if (k >= dep[x] - 1) return 1;
	while (dep[x] - dep[top[x]] + 1 <= k) {
		k -= dep[x] - dep[top[x]] + 1;
		x = fa[top[x]];
	}
	return seq[dfn[x] - k];
}
namespace seg {
struct node {
	int p1, p2, d;
	node() {}
	explicit node(int x): p1(x), p2(x), d(0) {}
	node(int p1, int p2): p1(p1), p2(p2), d(dist(p1, p2)) {}
	inline bool operator<(const node &t) const { return d < t.d; }
} val[$t];
int ll, rr; node vv;
node operator+(const node &A, const node &B) {
	if (!A.p1) return B;
	if (!B.p1) return A;
	return std::max(std::max(A, B), std::max(
		std::max(node(A.p1, B.p1), node(A.p1, B.p2)),
		std::max(node(A.p2, B.p1), node(A.p2, B.p2))
	));
}
void $update(int x, int l, int r) {
	if (l == r) return (void)(val[x] = vv);
	G; (ll <= mid)? $update(LL): $update(RR);
	val[x] = val[ls] + val[rs];
}
inline void insert(int i) { ll = i; vv = node(seq[i]); $update(1, 1, n); }
inline void remove(int i) { ll = i; vv = node(0); $update(1, 1, n); }
void $query(int x, int l, int r) {
	if (ll <= l && r <= rr) return (void)(vv = vv + val[x]);
	G; if (ll <= mid) $query(LL); if (mid < rr) $query(RR);
}
inline node query(int l, int r) { ll = l; rr = r; vv = node(0); $query(1, 1, n); return vv; }
} // namespace seg
namespace bit {
int v[$n];
inline void update(int x, int t) { while (x <= n) { v[x] += t; x += x & -x; } }
inline int query(int x) { int r = 0; while (x) { r += v[x]; x &= x - 1; } return r; }
inline int query(int l, int r) { return query(r) - query(l - 1); }
} // namespace bit
inline int far(int x, int v) {
	assert(contains(x, v));
	if (siz[x] == 1) return INT_MIN;
	auto t = seg::query(dfn[x], dfn[x] + siz[x] - 1);
	assert(t.p1 && t.p2);
	return std::max(dist(t.p1, v), dist(t.p2, v));
}
int main() {
	n = R; m = R;
	for (int i = 1; i < n; ++i) {
		const int x = R, y = R;
		outs[x].push_back(y);
		outs[y].push_back(x);
	}
	dfs(1); load(1, 1); int c = 0;
	while (m--) switch (R) {
		case 1: {
			int x = R, y = R, l = lca(x, y);
			bit::update(dfn[x], 1); bit::update(dfn[y], 1);
			bit::update(dfn[l], -1); ++c;
			if (!cnt[l]++) seg::insert(dfn[l]);
			break;
		}
		case 2: {
			int x = R, y = R, l = lca(x, y);
			bit::update(dfn[x], -1); bit::update(dfn[y], -1);
			bit::update(dfn[l], 1); --c;
			if (!--cnt[l]) seg::remove(dfn[l]);
			break;
		}
		case 3: {
			auto &t = seg::val[1];
			const int d = R, p = dep[t.p1] > dep[t.p2]? t.p1: t.p2;
			const int v = kth(p, d), y = kth(v, d);
			if (
				bit::query(dfn[y], dfn[y] + siz[y] - 1) == c &&
				far(y, v) <= d
			) pc('Y'), pc('e'), pc('s');
			else pc('N'), pc('o');
			pc('\n'); break;
		}
	}
}