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;

typedef long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

typedef pair < int , int > pii;

const int MN = 4e5 + 5 , LOG = 20;

int N , Q , o[MN] , id[MN] , eid[MN] , dfn , dep[MN] , cnt[MN];
vector < int > g[MN];
int ID[MN] , lg[MN << 1] , tot , st[MN << 1][LOG] , up[MN][LOG] , fa[MN];

inline void dfs(int u) {
	o[id[u] = ++dfn] = u; st[ID[u] = ++tot][0] = u;
	up[u][0] = fa[u];
	for (int i = 1; i < LOG; ++i) up[u][i] = up[up[u][i - 1]][i - 1];
	for (int v : g[u]) if (v != fa[u]) {
		fa[v] = u , dep[v] = dep[u] + 1;
	    dfs(v) , st[++tot][0] = u;
	}
	eid[u] = dfn;
}
inline int cmp(int x, int y) {return dep[x] > dep[y] ? y : x;}
inline void build(int n) {
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int k = 1; k < LOG; ++k)
    for (int i = 1; i <= n - (1 << k) + 1; ++i) 
      st[i][k] = cmp(st[i][k - 1], st[i + (1 << k - 1)][k - 1]);
}
inline int LCA(int u, int v) {
  if (id[u] > id[v]) swap(u, v);
  u = ID[u], v = ID[v]; int t = lg[v - u + 1];
  return cmp(st[u][t], st[v - (1 << t) + 1][t]);
}
inline int dist(int u , int v) {
	return (u && v) ? dep[u] + dep[v] - 2 * dep[LCA(u, v)] : -1;
}
inline int jump(int u , int d) {
  if (dep[u] <= d) return 1;
  for (; d; d &= d - 1) u = up[u][__builtin_ctz(d)];
  return u;
}
struct BIT {
  int sum[MN];
  inline void add(int x, int y) {for (; x <= N; x += x & -x) sum[x] += y;}
  inline int query(int x) {int res = 0; for (; x; x -= x & -x) res += sum[x]; return res;}
  inline int query(int l, int r) { return query(r) - query(l - 1);}
} tr;

struct node {
  int x, y, z;
  node(int _x = 0, int _y = 0) {x = _x, y = _y, z = dist(x, y);}
  inline friend bool operator < (const node &A, const node &B) { return A.z < B.z; }
  inline friend node operator ^ (const node &A, const node &B) { return std::max({A, B, node(A.x, B.x), node(A.x, B.y), node(A.y, B.x), node(A.y, B.y)});}
} diam[MN << 2];

void modify(int p, int l, int r, int pos, bool tp) {
  if (l == r) return void(diam[p] = node(tp * o[pos], tp * o[pos]));
  int mid = l + r >> 1; mid >= pos ? modify(p << 1, l, mid, pos, tp) : modify(p << 1 | 1, mid + 1, r, pos, tp);
  diam[p] = diam[p << 1] ^ diam[p << 1 | 1];
}
node query(int p, int l, int r, int L, int R) {
  if (l >= L && r <= R) return diam[p];
  int mid = l + r >> 1;
  if (mid >= L && mid < R) return query(p << 1, l, mid, L, R) ^ query(p << 1 | 1, mid + 1, r, L, R);
  if (mid >= L) return query(p << 1, l, mid, L, R);
  return query(p << 1 | 1, mid + 1, r, L, R);
}

set < pii > S;

int main() {
 	 
	 scanf("%d%d" , &N , &Q);
	 for (int i = 1 , u , v; i < N; ++i) {
	 	 scanf("%d%d" , &u , &v);
	 	 g[u].emplace_back(v) , g[v].emplace_back(u);
	 }
	 dfs(1) , build(tot);
	 for (int i = 1 , op , x , y , c = 0; i <= Q; ++i) {
	 	 scanf("%d%d" , &op , &x);
	 	 if (op == 3) {
	 	 	int v = jump(S.rbegin()->second, x), v1 = jump(v, x);
	        if (tr.query(id[v1], eid[v1]) != c) {puts("No"); continue;}
	        node tmp = query(1 , 1 , N , id[v1] , eid[v1]);
	        puts(std::max(dist(tmp.x, v), dist(tmp.y, v)) > x ? "No" : "Yes"); 
		 } else {
		 	 scanf("%d", &y); int z = LCA(x, y);
	         if (op == 1) {
	       		 ++c; if (!cnt[z]++) S.insert({dep[z], z}), modify(1, 1, N, id[z], 1);
	        	 tr.add(id[x], 1), tr.add(id[y], 1), tr.add(id[z], -1);
	      	 } else {
	        	--c; if (!--cnt[z]) S.erase({dep[z], z}), modify(1, 1, N, id[z], 0);
	        	tr.add(id[x], -1), tr.add(id[y], -1), tr.add(id[z], 1);
	         }
		 }
	 }
     return 0;
}