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:
// O(nlogn) - O(1) LCA
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define mp make_pair
const int maxn = 200200;
vector <int> e[maxn];
int dep[maxn], dfs_seq[maxn * 2], idx, L[maxn], Log[maxn * 2], st[20][maxn * 2];
struct node {
    int x, y, id;
    bool operator < (const node & a) const {
        return x < a.x || (x == a.x && y < a.y) || (x == a.x && y == a.y && id < a.id);
    }
};
struct diam {
    int d, u, v;
    bool operator < (const diam & a) const {
        return d < a.d || (d == a.d && u < a.u) || (d == a.d && u == a.u && v < a.v);
    }
} d[maxn * 4];
vector <pii> tr[maxn * 4];
int Q[maxn], D[maxn];
bool has_query[maxn * 4];
void dfs(int u, int p) {
    dfs_seq[++idx] = u;
    L[u] = idx;
    for (int i=0; i<e[u].size(); i++) {
        int v = e[u][i];
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        dfs_seq[++idx] = u;
    }
}
void init_lca() {
    Log[0] = -1; for (int i=1; i<=idx; i++) Log[i] = Log[i/2] + 1;
    for (int i=1; i<=idx; i++) st[0][i] = dfs_seq[i];
    for (int i=1; i<20; i++) {
        for (int j=1; j+(1<<i)-1<=idx; j++) {
            if (dep[st[i-1][j]] <= dep[st[i-1][j+(1<<i-1)]]) st[i][j] = st[i-1][j];
            else st[i][j] = st[i-1][j+(1<<i-1)];
        }
    }
}
int lca(int u, int v) {
    if (L[v] < L[u]) swap(u, v);
    int l = Log[L[v] - L[u] + 1];
    if (dep[st[l][L[u]]] <= dep[st[l][L[v]-(1<<l)+1]]) {
        return st[l][L[u]];
    }
    return st[l][L[v]-(1<<l)+1];
}
int dis(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

// closest node from x to (u, v) -> (id, dis)
pii closest_pt(int x, int u, int v) {
    int lu = lca(x, u), lv = lca(x, v);
    if (lu == lv) {
        int l = lca(u, v);
        return mp(l, dis(l, x));
    }
    if (dep[lu] < dep[lv]) swap(lu, lv);
    return mp(lu, dis(lu, x));
}
void add(int L, int R, pii path, int l, int r, int rt) {
    if (L <= l && r <= R) {
        tr[rt].push_back(path);
        return ;
    }
    int mid = (l + r) / 2;
    if (L <= mid) add(L, R, path, l, mid, rt<<1);
    if (mid < R) add(L, R, path, mid+1, r, rt<<1|1);
}
void add_query(int p, int l, int r, int rt) {
    has_query[rt] = true;
    if (l == r) return ;
    int mid = (l + r) / 2;
    if (p <= mid) add_query(p, l, mid, rt<<1);
    else add_query(p, mid+1, r, rt<<1|1);
}
void solve(int l, int r, int rt) {
//    printf("%d : [%d, %d] : ", rt, l, r);
//    for (int i=0; i<tr[rt].size(); i++) printf("(%d, %d) ", tr[rt][i].first, tr[rt][i].second); puts("");
    // solve it
    if (!has_query[rt]) return ;
    if (rt == 1) d[rt] = (diam){-1, -1, -1};
    else d[rt] = d[rt/2];
    for (int i=0; i<tr[rt].size(); i++) {
//        printf("  now d = %d, (%d, %d), add (%d, %d)\n", d[rt].d, d[rt].u, d[rt].v, tr[rt][i].first, tr[rt][i].second);
        if (d[rt].d == -1) {
            // no path
            d[rt] = (diam){0, tr[rt][i].first, tr[rt][i].second};
        } else if (d[rt].d == 0) {
            // (u, v) is intersection
            pii x = closest_pt(tr[rt][i].first, d[rt].u, d[rt].v);
            pii y = closest_pt(tr[rt][i].second, d[rt].u, d[rt].v);
//            printf("    x id %d, dis %d\n", x.first, x.second);
//            printf("    y id %d, dis %d\n", y.first, y.second);
            if (x.first != y.first) {
                d[rt] = (diam){0, x.first, y.first};
            } else {
                pii U = closest_pt(x.first, tr[rt][i].first, tr[rt][i].second);
                d[rt] = (diam){U.second, x.first, U.first};
            }
        } else {
            // no intersection, (u, v) is diameter
            pii x = closest_pt(tr[rt][i].first, d[rt].u, d[rt].v);
            pii y = closest_pt(tr[rt][i].second, d[rt].u, d[rt].v);
            if (x.first != y.first) continue;
            pii U = closest_pt(x.first, tr[rt][i].first, tr[rt][i].second);

            int d1 = dis(U.first, d[rt].u), d2 = dis(U.first, d[rt].v);
            if (d[rt].d >= d1 && d[rt].d >= d2) ; // empty
            else if (d1 > d2) d[rt] = (diam){d1, U.first, d[rt].u};
            else d[rt] = (diam){d2, U.first, d[rt].v};
        }
    }
//    printf("d[%d] = %d, (%d, %d)\n", rt, d[rt].d, d[rt].u, d[rt].v);

    if (l == r) {
        D[l] = d[rt].d;
        return ;
    }
    int mid = (l + r) / 2;
    solve(l, mid, rt<<1);
    solve(mid+1, r, rt<<1|1);
}
int main(void) {
    //freopen("f.in", "r", stdin);
    int n, q; scanf("%d%d", &n, &q);
    for (int i=1; i<n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    set <node> Set;
    for (int i=1; i<=q; i++) {
        int op, x, y; scanf("%d", &op);
        if (op == 1 || op == 2) {
            scanf("%d%d", &x, &y);
            if (x > y) swap(x, y);
            if (op == 1) {
                Set.insert((node){x, y, i});
            } else {
                set <node>::iterator it = Set.lower_bound((node){x, y, 0});
                add(it->id, i-1, mp(it->x, it->y), 1, q, 1);
                Set.erase(it);
            }
            Q[i] = -1;
        } else {
            scanf("%d", &x);
            Q[i] = x;
            add_query(i, 1, q, 1);
        }
    }
    for (set<node>::iterator it=Set.begin(); it != Set.end(); ++it) {
        add(it->id, q, mp(it->x, it->y), 1, q, 1);
    }
    dfs(1, 0);
    init_lca();

//    for (int i=0; i<4; i++) {
//        printf("st[%d] : ", i);
//        for (int j=1; j<=idx; j++) printf("%d ", st[i][j]); puts("");
//    }

    solve(1, q, 1);
    for (int i=1; i<=q; i++) if (~Q[i]) {
        puts((2 * Q[i] >=  D[i]) ? "Yes" : "No");
    }
    return 0;
}