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 <cstdio>
#include <cstring>
#include <iostream>

#define d isdigit(c)
#define g c=t.get();
#define L return
#define K break
#define A(c,a,b)if(c)a else b;
#define I(c,a)if(c)a;
#define Y goto E
struct MI{private:char bb[1 << 14];FILE*f;char*bs,*be;char e;bool o,l;public:MI():f(stdin),bs(0),be(0){}
#ifdef __linux__
#endif
inline char get(){if(o){o=0;L e;}
#ifdef MIVIK
char c=fgetc(f);I(c==-1,l=1)L c;
#else
I(bs==be,be=(bs=bb)+fread(bb,1,sizeof(bb),f))I(bs==be,{l=1;L-1;})L*bs++;
#endif
}inline void unget(char c){o=1;e=c;}template<class T>inline T read(){T r;*this>r;L r;}template<class T>inline MI&operator>(T&);};template<class T>struct Q{const static bool U=T(-1)>=T(0);inline void operator()(MI&t,T&r)const{r=0;char c;bool y=0;A(U,for(;;){g I(c==-1,Y)I(d,K)},for(;;){g I(c==-1,Y)A(c=='-',{g I(d,{y=1;K;})},I(d,K))})for(;;){I(c==-1,Y)A(d,r=r*10+(c^48);,K)g}t.unget(c);E:;I(y,r=-r)}};template<>struct Q<char>{};template<class T>inline MI&MI::operator>(T&t){Q<T>()(*this,t);L*this;}
#undef d
#undef g
#undef L
#undef K
#undef A
#undef I
#undef Y
template<class T>std::ostream& operator<(std::ostream&out,const T&t){return out<<t;}
#define endl ('\n')
#define P(x) cout<#x" = "<(x)<endl
#define R (cin.read<int>())

using std::cout;

#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

#include <vector>
#include <climits>
#include <cassert>
#include <set>

MI cin;

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

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
struct cmp_t {
	inline bool operator()(int x, int y) const {
		if (int d = dep[x] - dep[y]) return d > 0;
		return x < y;
	}
};
std::set<int, cmp_t> w;
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() {
	cin > n > m;
	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]++) w.insert(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]) w.erase(l), seg::remove(dfn[l]);
				break;
			}
			case 3: {
				const int d = R, p = *w.begin();
				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)
					cout < "Yes\n";
				else
					cout < "No\n";
				break;
			}
		}
}