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 rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)

typedef double         db;
typedef long long      ll;
typedef pair<int, int> ii;
typedef pair<ii, int>  iii;
typedef vector<int>    vi;
typedef vector<ii>     vii;
typedef vector<iii>    viii;

struct Fenwick {
	int n;
	vi t;
	Fenwick(int n) : n(n), t(n) {}
	void upd(int v, int x) {
		for (int i = v; i < n; i |= i + 1) {
			t[i] += x;
		}
	}
	int get(int v) {
		int res = 0;
		for (int i = v; i >= 0; i = (i & (i + 1)) - 1) {
			res += t[i];
		}
		return res;
	}
	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

struct SegTree {
	const int inf = 1e9;
	int n;
	vi t;
	SegTree(int n) : n(n), t(2 * n, -inf) {}
	int plus(int x, int y) {
		return max(x, y);
	}
	void upd(int v, int x) {
		t[v += n] = x;
		for (v >>= 1; v; v >>= 1) {
			t[v] = plus(t[v << 1], t[v << 1 | 1]);
		}
	}
	int get(int l, int r) {
		int ret = -inf;
		for (l += n, r += n; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
			if (l & 1) {
				ret = plus(ret, t[l]);
			}
			if (!(r & 1)) {
				ret = plus(ret, t[r]);
			}
		}
		return ret;
	}
};

struct Tree{
	private:
		int n;
		int root;
		int tmp;
		vector<vi> adj;
		vector<vi> fa;
		// record 2^i up steps 
		vi sz;
		vi depth;
		vi dfs_seq;
		vi i_dfs_seq;
		vi r_dfs_seq;
		vi top;
        // 
        Fenwick v1;
		
        SegTree tr, tr2;
        vi v2;
        vector<multiset<int>> dset;
		
	public:
		Tree(): v1(0), tr(0), tr2(0) {
			n = 0;
		}

		Tree(int n, int rt=0): v1(n), tr(n), tr2(n) {
			this->n = n;
			root = rt;
			depth.resize(n);
			sz.resize(n);
			adj.resize(n);
			dfs_seq.resize(n);
			i_dfs_seq.resize(n);
			r_dfs_seq.resize(n);
			top.resize(n);
			int n2 = 1, i2 = 1;
			while (2 * n2 - 1 < n) n2 *= 2, i2++;
			fa = vector<vi>(i2, vi(n, -1));

            v2.resize(n);
            dset.resize(n);
		}

        int ask(int k, int g) {
			int g2 = g;
			int ans = -tr.inf;
			int l = i_dfs_seq[g];
			int r = r_dfs_seq[g];
            while (true) {
				if (g2 != g) {
					ans = max(ans, tr2.get(i_dfs_seq[g], r) - 2*depth[g]);
					ans = max(ans, tr2.get(l, r_dfs_seq[g]) - 2*depth[g]);
				}
				if (g==top[g]) {
					r = i_dfs_seq[top[g]] - 1;
					l = r_dfs_seq[top[g]] + 1;
					g = fa[0][top[g]];
				} else 
				if (top[g] == top[k]) {	
					ans = max(ans, tr.get(i_dfs_seq[k], i_dfs_seq[g]-1));
					break;
				} else {
					ans = max(ans, tr.get(i_dfs_seq[top[g]], i_dfs_seq[g]-1));
					r = i_dfs_seq[top[g]] - 1;
					l = r_dfs_seq[top[g]] + 1;
					g = fa[0][top[g]];
				} 
				if (g<0 || depth[g]<depth[k]) break;
			}
            return ans + depth[g2];
        }

        int ask_v1(int x) {
            return v1.get(i_dfs_seq[x], r_dfs_seq[x]);
        }

        void upd_v1(int x, int y) {
            v1.upd(i_dfs_seq[x], y);
        }

        void upd_v2(int x, int y) {
            int d = depth[x];
            v2[x] += y;
            if (y>0 && v2[x]==1) {
				tr2.upd(i_dfs_seq[x], d);
                while (x >= 0) {
                    x = fa[0][top[x]];
                    if (x >= 0) {
                        dset[x].insert(d - 2*depth[x]);
                        tr.upd(i_dfs_seq[x], *(dset[x].rbegin()));
                    }
                }
            }
            if (y<0 && v2[x]==0) {
				tr2.upd(i_dfs_seq[x], -tr2.inf);
                while (x >= 0) {
                    x = fa[0][top[x]];
                    if (x >= 0) {
                        dset[x].erase(dset[x].find(d - 2*depth[x]));
                        if (dset[x].empty()) 
                            tr.upd(i_dfs_seq[x], -tr.inf);
                        else 
                            tr.upd(i_dfs_seq[x], *(dset[x].rbegin()));
                    }
                }
            }
        }

		void add_edge(int x, int y) {
			adj[x].push_back(y);
			adj[y].push_back(x);
		}

		int get_root() {
			return root;
		}

		int get_depth(int x) {
			return depth[x];
		}

		pair<int, int> get_subtree(int x) {
			return make_pair(i_dfs_seq[x], r_dfs_seq[x]);
		}

		void dfs(int x, int y=-1) {
			sz[x] = 1;
			fa[0][x] = y;
			depth[x] = (y >= 0) ? depth[y] + 1 : 0;
			for(auto i: adj[x]) 
				if (i != y) 
					dfs(i, x), sz[x] += sz[i];
		}

		void dfs_hld(int x, int y=-1) {
			if (y==-1) 
				tmp = 0, top[x] = x;
			i_dfs_seq[x] = tmp;
			dfs_seq[tmp++] = x;
			int j; 
			int sj = -1;
			for(auto i: adj[x]) 
				if (i != y && sz[i] > sj) 
					j = i, sj = sz[i];
			if (sj > 0) 
				top[j] = top[x], dfs_hld(j, x);
			for(auto i: adj[x])
				if (i != y && i != j) 
					top[i] = i, dfs_hld(i, x);
			r_dfs_seq[x] = tmp - 1;
			return;
		}

		void fa_2k() {
			rep(i, 0, (int)fa.size()-2)
				rep(j, 0, n-1) 
					if (fa[i][j] < 0) {
						fa[i+1][j] = -1;
					} else {
						fa[i+1][j] = fa[i][fa[i][j]];
					}
		}
		
		int lca(int x, int y) {
			while (top[x] != top[y]) {
				if (depth[top[x]] < depth[top[y]]) swap(x, y);
				x = fa[0][top[x]];
			}
			return (depth[x] < depth[y]) ? x : y;
		}

        int go_up(int x, int y) {
            y = min(y, depth[x]);
            per(i, (int)fa.size()-1, 0) 
                if (y >= (1 << i)) 
                    x = fa[i][x], y -= (1 << i);
            return x;            
        }
};

int main() {
    // freopen("in3.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    Tree tree(n);
    rep(i, 1, n-1) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        tree.add_edge(x, y);
    }
    tree.dfs(tree.get_root());
    tree.dfs_hld(tree.get_root());
    tree.fa_2k();

    multiset<pair<int, int> > lcaset;

    for(;m--;) {
        int opt, u, v, lp, d;
        cin >> opt;
        if (opt==1) {
            cin >> u >> v;
            u--; v--;
            lp = tree.lca(u ,v);
            lcaset.insert(make_pair(tree.get_depth(lp), lp));
            tree.upd_v1(u, 1);
            tree.upd_v1(v, 1);
            tree.upd_v1(lp, -1);
            tree.upd_v2(lp, 1);
        } else
        if (opt==2) {
            cin >> u >> v;
            u--; v--;
            lp = tree.lca(u, v);
            lcaset.erase(lcaset.find(make_pair(tree.get_depth(lp), lp)));
            tree.upd_v1(u, -1);
            tree.upd_v1(v, -1);
            tree.upd_v1(lp, 1);
            tree.upd_v2(lp, -1);
        } else {
            cin >> d;
            lp = (*lcaset.rbegin()).second;
            int g, k;
            g = tree.go_up(lp, d);
            k = tree.go_up(g, d);
            if (tree.ask_v1(k) != lcaset.size()) cout << "No" << endl;
            else {
                if (tree.ask(k, g) <= d) cout << "Yes" << endl;
                else cout << "No" << endl;
            } 
        }
    }
    return 0;
}