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>
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int N = 200003;
template<typename T>
void read(T &x){
    int ch = getchar(); x = 0;
    for(;ch < '0' || ch > '9';ch = getchar());
    for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
int n, q, cnt, tcnt, ocr[N], head[N], to[N<<1], nxt[N<<1];
void add(int a, int b){to[++cnt] = b; nxt[cnt] = head[a]; head[a] = cnt;}
int siz[N], fa[N], dep[N], wson[N];
void dfs1(int x){
    siz[x] = 1;
    for(int i = head[x];i;i = nxt[i]) if(to[i] != fa[x]){
        dep[to[i]] = dep[x] + 1;
        fa[to[i]] = x; dfs1(to[i]);
        siz[x] += siz[to[i]];
        if(siz[wson[x]] < siz[to[i]]) wson[x] = to[i];
    }
}
int dfn[N], pre[N], top[5][N], tim;
void dfs2(int x, int tp){
    dfn[x] = ++tim; pre[tim] = x; top[0][x] = tp;
    for(int i = 1;i < 5;++ i) top[i][x] = top[i-1][fa[top[i-1][x]]];
    if(wson[x]){
        dfs2(wson[x], tp);
        for(int i = head[x];i;i = nxt[i])
            if(to[i] != fa[x] && to[i] != wson[x])
                dfs2(to[i], to[i]);
    }
}
int ask(int x, int k){
    for(int i = 4;~i;-- i)
        if(k > dep[x] - dep[top[i][x]]){
            k -= dep[x] - dep[top[i][x]] + 1;
            x = fa[top[i][x]];
        }
    return pre[max(1, dfn[x] - k)];
}
int lca(int u, int v){
    while(top[0][u] != top[0][v]){
        if(dep[top[0][u]] < dep[top[0][v]]) swap(u, v);
        u = fa[top[0][u]];
    } return dep[u] < dep[v] ? u : v;
}
int dis(int u, int v){
    if(u == -1 || v == -1) return 0;
    return dep[u] + dep[v] - (dep[lca(u,v)]<<1);
}
struct Node {
    int u, v, len;
    Node(int _u = -1, int _v = -1, int _len = 0): u(_u), v(_v), len(_len){}
    Node operator + (const Node &o) const {
        if(u == -1) return o; if(o.u == -1) return *this;
        Node res = len > o.len ? *this : o;
        int tmp = dis(u, o.u); if(chmax(res.len, tmp)){res.u = u; res.v = o.u;}
        tmp = dis(u, o.v); if(chmax(res.len, tmp)){res.u = u; res.v = o.v;}
        tmp = dis(v, o.u); if(chmax(res.len, tmp)){res.u = v; res.v = o.u;}
        tmp = dis(v, o.v); if(chmax(res.len, tmp)){res.u = v; res.v = o.v;}
        return res;
    }
} seg[N<<2];
void upd(int x, int L, int R, int p, bool op){
    if(L == R){seg[x].u = seg[x].v = op ? pre[L] : -1; return;}
    int mid = L + R >> 1;
    if(p <= mid) upd(x<<1, L, mid, p, op);
    else upd(x<<1|1, mid+1, R, p, op);
    seg[x] = seg[x<<1] + seg[x<<1|1];
}
Node qry(int x, int L, int R, int l, int r){
    if(l <= L && R <= r) return seg[x];
    int mid = L + R >> 1;
    if(r <= mid) return qry(x<<1, L, mid, l, r);
    if(mid < l) return qry(x<<1|1, mid+1, R, l, r);
    return qry(x<<1, L, mid, l, r) + qry(x<<1|1, mid+1, R, l, r);
}
int tr[N];
void upd(int p, int v){for(;p <= n;p += p & -p) tr[p] += v;}
int qry(int p){int r = 0; for(;p;p -= p & -p) r += tr[p]; return r;}
multiset<pii> S;
bool calc(){
    int d; read(d); int l = S.rbegin()->se, u = ask(l, d), v = ask(u, d);
    if(qry(dfn[v]+siz[v]-1) - qry(dfn[v]-1) != tcnt) return false;
    Node tmp = qry(1, 1, n, dfn[v], dfn[v]+siz[v]-1);
    return dis(tmp.u, u) <= d && dis(tmp.v, u) <= d;
}
int main(){
    read(n); read(q);
    for(int i = 1, u, v;i < n;++ i){
        read(u); read(v); add(u, v); add(v, u);
    } fa[1] = 1; dfs1(1); dfs2(1, 1);
    while(q --){
        int op; read(op);
        if(op <= 2){
            int u, v; read(u); read(v);
            int w = lca(u, v); pii pt = MP(dep[w], w);
            if(op == 1){
                if(!ocr[w]) upd(1, 1, n, dfn[w], true); ++ ocr[w];
                upd(dfn[u], 1); upd(dfn[v], 1); upd(dfn[w], -1); ++ tcnt;
                S.insert(pt);
            } else {
                -- ocr[w]; if(!ocr[w]) upd(1, 1, n, dfn[w], false);
                upd(dfn[u], -1); upd(dfn[v], -1); upd(dfn[w], 1); -- tcnt;
                S.erase(S.find(pt));
            }
        } else puts(calc() ? "Yes" : "No");
    }
}