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;
const int N = 200005;
using ll = long long;
int n,qq;vector<int> v[N];
int fa[N],sz[N],hson[N],dep[N],top[N],id[N],didx;
void dfs1(int pos,int f)
{
    fa[pos] = f;dep[pos] = dep[f] + 1;sz[pos] = 1;
    for (auto &i : v[pos])
        if (i != f) { dfs1(i,pos);sz[pos] += sz[i];if (sz[i] > sz[hson[pos]]) hson[pos] = i; }
}
int dfn[N],rdfn[N];
void dfs2(int pos,int tp)
{
    id[dfn[pos] = ++didx] = pos;top[pos] = tp;if (hson[pos]) dfs2(hson[pos],tp);
    for (auto &i : v[pos])
        if (i != fa[pos] && i != hson[pos]) dfs2(i,i);
    rdfn[pos] = didx;
}
int lca(int x,int y)
{
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x,y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
int kanc(int x,int kk)
{
    while (dep[x] - dep[top[x]] + 1 <= kk) kk -= dep[x] - dep[top[x]] + 1,x = fa[top[x]];
    return id[dfn[x] - kk];
}
struct SegTree
{
    int t[N << 2],m;
    void init()
    {
        for (m = 1;m < n + 2;m <<= 1);
        for (int i = 1;i < m * 2;i++) t[i] = INT_MIN >> 1;
    }
    void modify(int x,int v)
    { t[x += m] = v;while (x >>= 1) t[x] = max(t[x << 1],t[x << 1 | 1]); }
    int query(int l,int r)
    {
        int ans = INT_MIN >> 1;
        for (l += m - 1,r += m + 1;r - l > 1;l >>= 1,r >>= 1)
        {
            if (!(l & 1)) ans = max(ans,t[l ^ 1]);
            if (r & 1) ans = max(ans,t[r ^ 1]);
        }
        return ans;
    }
    inline int mx()
    {
        int pos = 1;while (pos < m) pos = pos << 1 | (t[pos << 1 | 1] == t[1]);
        return pos - m;
    }
} t1,t2;
int cnt[N],sum;
inline void modify1(int x,int v)
{ cnt[x] += v;sum += v;t1.modify(dfn[x],cnt[x] ? dep[x] : INT_MIN >> 1); }
void modify2(int x)
{
    while (x)
    {
        if (dfn[x] < rdfn[x])
            t2.modify(dfn[x],t1.query(rdfn[hson[x]] + 1,rdfn[x]) - dep[x] * 2);
        x = fa[top[x]];
    }
}
struct BIT
{
    inline int lowbit(int x) {return x & -x;}
    int c[N];
    void add(int x,int v) { while (x <= n) c[x] += v,x += lowbit(x); }
    int query(int x)
    {
        int ret = 0;while (x) ret += c[x],x -= lowbit(x);
        return ret;
    }
    inline int query(int l,int r) {return query(r) - query(l - 1);}
} b1,b2;
bool check(int x,int d)
{
    int y = x,lst = 0;
    while (y)
    {
        if (t2.query(dfn[top[y]],dfn[y] - 1) + dep[x] > d) return 0;
        if ((lst ? max(t1.query(dfn[y] + 1,dfn[lst] - 1),t1.query(rdfn[lst] + 1,rdfn[y]))
            + dep[x] - dep[y] * 2 : t1.query(dfn[y] + 1,rdfn[y]) - dep[x]) > d) return 0;
        y = fa[lst = top[y]];
    }
    return 1;
}
bool check2(int x)
{ return sum == b1.query(dfn[x],rdfn[x]) - b2.query(dfn[x],rdfn[x]); }
int main ()
{
    ios::sync_with_stdio(false);
    cin >> n >> qq;int x1,x2;
    for (int i = 1;i < n;i++)
        cin >> x1 >> x2,v[x1].push_back(x2),v[x2].push_back(x1);
    dfs1(1,0);dfs2(1,1);t1.init();t2.init();
    while (qq--)
    {
        cin >> x1 >> x2;
        if (x1 < 3)
        {
            int x3;cin >> x3;int z = lca(x2,x3);x1 = x1 == 1 ? 1 : -1;
            modify1(z,x1);modify2(z);
            b1.add(dfn[x2],x1);b1.add(dfn[x3],x1);b2.add(dfn[z],x1);
        }
        else
        {
            bool fl = 1;int dd = x2;x2 = id[t1.mx()];
            if (dep[x2] - dep[1] > dd)
            {
                x2 = kanc(x2,dd);fl &= check(x2,dd);
                if (dep[x2] - dep[1] > dd) fl &= check2(kanc(x2,dd));
            }
            cout << (fl ? "Yes" : "No") << endl;
        }
    }
    return 0;
}