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 <cstdio>
#include <algorithm>
#include <set>

int read() {
  static int c, x;
  while ((c = getchar()) < 48) {}
  x = c & 15;
  while ((c = getchar()) >= 48) x = x * 10 + (c & 15);
  return x;
}

#define MAXN 200010

struct edge {
  int next, to;
} e[MAXN << 1];
struct node {
  int x, y, l;
  constexpr node() : x(), y(), l() {}
  constexpr node(const int &x, const int &y, const int &l)
      : x(x), y(y), l(l) {}
};

typedef int arr[MAXN];

int n, N;
arr head, hson, siz, dfn, seg, tr, top, dep, fa, vis;
node sgt[MAXN << 2];

struct cmp {
  inline bool operator()(const int &x, const int &y) const {
    return (dep[x] != dep[y]) ? (dep[x] > dep[y]) : (x < y);
  }
};

std::set<int, cmp> st;

inline void add(const int &x, const int &y) {
  static int ei;
  e[++ei].next = head[x];
  e[ei].to = y;
  head[x] = ei;
}

template <int v>
void plus(int x) {
  while (x <= n) {
    tr[x] += v;
    x += x & -x;
  }
}
int query(int l, int r) {
  --l;
  int ans = 0;
  while (r > l) {
    ans += tr[r];
    r &= r - 1;
  }
  while (l > r) {
    ans -= tr[l];
    l &= l - 1;
  }
  return ans;
}

void dfs1(const int &f) {
  dep[f] = dep[fa[f]] + 1;
  siz[f] = 1;
  for (int i = head[f]; i; i = e[i].next) {
    const int t = e[i].to;
    if (t == fa[f]) continue;
    fa[t] = f;
    dfs1(t);
    siz[f] += siz[t];
    if (siz[t] > siz[hson[f]]) hson[f] = t;
  }
}
void dfs2(const int &f) {
  static int cnt;
  seg[++cnt] = f;
  dfn[f] = cnt;
  if (!hson[f]) return;
  top[hson[f]] = top[f];
  dfs2(hson[f]);
  for (int i = head[f]; i; i = e[i].next) {
    const int t = e[i].to;
    if (t == fa[f] || t == hson[f]) continue;
    top[t] = t;
    dfs2(t);
  }
}
int lca(int x, int y) {
  while (top[x] != top[y]) {
    (dep[top[x]] < dep[top[y]]) ? (y = fa[top[y]]) : (x = fa[top[x]]);
  }
  return (dep[x] < dep[y]) ? x : y;
}
inline int dist(const int &x, const int &y) {
  return dep[x] + dep[y] - (dep[lca(x, y)] << 1);
}
int kthanc(int x, int k) {
  if (dep[x] <= k + 1) return 1;
  while (dep[x] - dep[top[x]] < k) {
    k -= dep[x] - dep[top[x]] + 1;
    x = fa[top[x]];
  }
  return seg[dfn[x] - k];
}

constexpr bool operator <(const node &x, const node &y) {
  return x.l < y.l;
}
inline node makenode(const int &x, const int &y) {
  return node(x, y, dist(x, y));
}
inline node operator *(const node &x, const node &y) {
  if (!x.x) return y;
  if (!y.x) return x;
  return std::max({ x, y, makenode(x.x, y.x), makenode(x.x, y.y),
    makenode(x.y, y.x), makenode(x.y, y.y) });
}

template <bool b>
void modify(int p) {
  if (b) {
    sgt[p + N].x = seg[p];
    sgt[p + N].y = seg[p];
    p += N;
  } else {
    p += N;
    sgt[p].x = 0;
  }
  while (p != 1) {
    p >>= 1;
    sgt[p] = sgt[p << 1] * sgt[p << 1 | 1];
  }
}
node sgtquery(int l, int r) {
  if (l == r) return sgt[l + N];
  static node ans;
  ans.x = 0;
  for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
    if (~l & 1) ans = ans * sgt[l ^ 1];
    if ( r & 1) ans = ans * sgt[r ^ 1];
  }
  return ans;
}

int main() {
  n = read();
  int q = read();
  for (int i = n; --i; ) {
    const int x = read(), y = read();
    add(x, y);
    add(y, x);
  }
  dfs1(1);
  top[1] = 1;
  dfs2(1);
  for (N = 1; N <= n + 1; N <<= 1) {}
  int cnt = 0;
  while (q--) {
    switch (read()) {
      case 1 : {
        const int x = read(), y = read(), l = lca(x, y);
        plus<1>(dfn[x]);
        plus<1>(dfn[y]);
        plus<-1>(dfn[l]);
        ++cnt;
        if (!vis[l]++) {
          st.insert(l);
          modify<true>(dfn[l]);
        }
        break;
      }
      case 2 : {
        const int x = read(), y = read(), l = lca(x, y);
        plus<-1>(dfn[x]);
        plus<-1>(dfn[y]);
        plus<1>(dfn[l]);
        --cnt;
        if (!--vis[l]) {
          st.erase(l);
          modify<false>(dfn[l]);
        }
        break;
      }
      case 3 : {
        const int k = read();
        const int x = kthanc(*st.cbegin(), k), y = kthanc(x, k);
        if (query(dfn[y], dfn[y] + siz[y] - 1) != cnt) {
          puts("No");
          break;
        }
        static node ans;
        ans = sgtquery(dfn[y], dfn[y] + siz[y] - 1);
        if (dist(ans.x, x) > k || dist(ans.y, x) > k) {
          puts("No");
          break;
        }
        puts("Yes");
        break;
      }
    }
  }
  return 0;
}