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:
// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 14;
vector<int> g[maxn];
int n, q, par[maxn], h[maxn], head[maxn], st[maxn], en[maxn], sz[maxn], ver[maxn];

struct SegmentMax {
    int seg[maxn * 2];

    SegmentMax() {
        fill(seg, end(seg), -maxn);
    }

    void upd(int v, int val) {
        v = st[v];
        for (seg[v += n] = val; v >>= 1;)
            seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
    }

    int get(int l, int r) {
        int ans = -maxn;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l % 2)
                ans = max(ans, seg[l++]);
            if (r % 2)
                ans = max(ans, seg[--r]);
        }
        return ans;
    }
} subtree, path;

struct Fenwick {
    int fen[maxn];

    void upd(int v, int val) {
        for (int p = st[v] + 1; p < maxn; p += p & -p)
            fen[p] += val;
    }

    int _get(int p) {
        int ans = 0;
        for (; p; p ^= p & -p)
            ans += fen[p];
        return ans;
    }

    int get(int v) {
        return _get(en[v]) - _get(st[v]);
    }
} fenwick;

int nxt(int v) {
    return head[v] == v ? par[v] : head[v];
}

int lca(int v, int u) {
    while (true) {
        if (st[v] <= st[u] and en[u] <= en[v])
            return v;
        swap(v, u);
        if (st[v] <= st[u] and en[u] <= en[v])
            return v;
        if (h[nxt(v)] < h[nxt(u)])
            u = nxt(u);
        else
            v = nxt(v);
    }
}

int par_at(int v, int par_h) {
    while (v and h[nxt(v)] >= par_h)
        v = nxt(v);
    return ver[st[v] + par_h - h[v]];
}

void pre_dfs(int v = 0) {
    sz[v] = 1;
    for (auto u : g[v]) {
        par[u] = v;
        h[u] = h[v] + 1;
        g[u].erase(find(g[u].begin(), g[u].end(), v));
        pre_dfs(u);
        sz[v] += sz[u];
    }
    if (!g[v].empty())
        swap(g[v][0], *max_element(g[v].begin(), g[v].end(), [](int v, int u) { return sz[v] < sz[u]; }));
}

void pre_hld(int v = 0) {
    static int dfs_time = 0;
    ver[dfs_time] = v;
    st[v] = dfs_time++;
    for (int i = 0; i < g[v].size(); ++i) {
        head[g[v][i]] = i ? g[v][i] : head[v];
        pre_hld(g[v][i]);
    }
    en[v] = dfs_time;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    pre_dfs();
    pre_hld();
    multiset<int, function<bool(int, int)>> lcas([](int v, int u) { return h[v] != h[u] ? h[v] > h[u] : v < u; });
    while (q--) {
        int t;
        cin >> t;
        if (t == 3) {
            int d;
            cin >> d;
            auto check = [&]() {
                if (lcas.empty())
                    return false;
                int v = par_at(*lcas.begin(), max(0, h[*lcas.begin()] - d));
                int p = par_at(v, max(0, h[v] - d));
                if (fenwick.get(p) < lcas.size() || subtree.get(st[v], en[v]) > h[v] + d)
                    return false;
                int hv = h[v];
                while (h[p] < h[v]) {
                    if (head[v] == v) {
                        if (max(subtree.get(st[par[v]], st[v]), subtree.get(en[v], en[par[v]])) + hv -
                            2 * h[par[v]] > d)
                            return false;
                    }
                    else if (path.get(max(st[head[v]], st[p]), st[v]) + hv > d)
                        return false;
                    v = nxt(v);
                }
                return true;
            };
            cout << (check() ? "Yes\n" : "No\n");
        }
        else {
            t = t == 1 ? 1 : -1;
            int v, u;
            cin >> v >> u;
            v--, u--;
            int p = lca(v, u);
            fenwick.upd(v, t);
            fenwick.upd(u, t);
            fenwick.upd(p, -t);
            bool change;
            if (t == 1) {
                change = lcas.find(p) == lcas.end();
                lcas.insert(p);
            }
            else {
                lcas.erase(lcas.find(p));
                change = lcas.find(p) == lcas.end();
            }
            if (change) {
                subtree.upd(p, t == 1 ? h[p] : -maxn);
                while (head[p]) {
                    p = head[p];
                    path.upd(par[p], subtree.get(en[g[par[p]][0]], en[par[p]]) - 2 * h[par[p]]);
                    p = par[p];
                }
            }
        }
    }
}