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>
#ifdef LOCAL
#include "debuger.hpp"
#else
#define DUMP(...) 1145141919810
#define CHECK(...) (__VA_ARGS__)
#endif

const int kN = 200000 + 5;
const int INF = 0x3f3f3f3f;
std::vector<int> edges[kN];
int n, q;
int header[kN],dfn[kN],tim,parent[kN],sz[kN];
int depth[kN];
int last[kN];

void get_sz(int u, int fa) {
  sz[u] = 1;
  for (int v : edges[u]) {
    if (v == fa) continue;
    depth[v] = depth[u] + 1;
    get_sz(v, u);
    sz[u] += sz[v];
  }
}

void rebuild(int u, int fa, int color) {
  dfn[u] = tim ++;
  parent[u] = fa;
  header[u] = color;
  last[color] = u;
  int p = -1;
  for (int v : edges[u]) {
    if (v == fa) continue;
    if (p == -1 || sz[v] > sz[p]) {
      p = v;
    }
  }
  if (p != -1) {
    rebuild(p, u, color);
  }
  for (int v : edges[u]) {
    if (v == fa || v == p) continue;
    rebuild(v, u, v);
  }
}

int get_lca(int a, int b) {
  while (header[a] != header[b]) {
    if (dfn[header[a]] < dfn[header[b]]) {
      std::swap(a,b);
    }
    a = parent[header[a]];
  }
  return dfn[a] < dfn[b] ? a : b;
}

struct SegmentTree {
  int mx[kN << 1];

  int get_id(int l, int r) const { return l + r | l != r; }
  void up(int l, int r) {
    if (l != r) {
      int mid = l + r >> 1;
      mx[get_id(l, r)] = std::max(mx[get_id(l, mid)], mx[get_id(mid + 1, r)]);
    }
  }
  void build(int l, int r) {
    mx[get_id(l, r)] = -INF;
    if (l != r) {
      int mid = l + r >> 1;
      build(l, mid);
      build(mid + 1, r);
    }
  }
  int query(int L, int R, int l, int r) const {
    if (r < L || R < l) return -INF;
    if (L <= l && r <= R) return mx[get_id(l, r)];
    int mid = l + r >> 1;
    return std::max(query(L, R, l, mid), query(L, R, mid + 1, r));
  }
  void modify(int p, int v, int l, int r) {
    if (l == r) {
      mx[get_id(l, r)] = v;
    } else {
      int mid = l + r >> 1;
      if (p <= mid) modify(p, v, l, mid);
      else modify(p, v, mid + 1, r);
      up(l, r);
    }
  }

} tree[2];  // 0: val-dfn[v], 1: val+dfn[v]

struct Fenwick {
  int arr[kN];

  void update(int p, int dt) { for (int i = p; i >= 0; i -= ~i & i + 1) arr[i] += dt; }
  int query(int p) const { int ret = 0; for (int i = p; i < kN; i += ~i & i + 1) ret += arr[i]; return ret; }

  void hld_update(int u, int dt) {
    while (u != -1) {
      update(dfn[u], dt);
      if (dfn[header[u]] > 0) {
        update(dfn[header[u]] - 1, -dt);
      }
      u = parent[header[u]];
    }
  }
} bit;

const int kLog = 19;
int pjump[kLog][kN];

void init_jump() {
  for (int i = 0; i < n; ++i) {
    pjump[0][i] = parent[i];
  }
  for (int i = 0; i + 1 < kLog; ++i) {
    for (int u = 0; u < n; ++u) {
      pjump[i + 1][u] = pjump[i][u] == -1 ? -1 : pjump[i][pjump[i][u]];
    }
  }
}

int jump(int u, int d) {
  for (int i = 0; i < kLog; ++i) {
    if (d >> i & 1) {
      u = pjump[i][u];
      if (u == -1) return 0;
    }
  }
  return u;
}

std::multiset<std::pair<int, int>> multiset;

std::multiset<int> virtual_sets[kN];

int hld_query(int u, int guard) {
  int ret = 0;
  int v = u;
  int prev_head = -1;
  while (v != -1 && dfn[v] >= dfn[guard]) {
    int w = header[v];
    if (dfn[w] < dfn[guard]) w = guard;
    int e = last[header[v]];

    if (!virtual_sets[v].empty()) {
      int homologous_val = -INF;
      if (prev_head != -1) {
        int val = tree[1].query(dfn[prev_head], dfn[last[prev_head]], 0, n - 1);
        if (val != -INF) {
          homologous_val = val - dfn[prev_head] + 1;
        }
      }
      if (homologous_val != *virtual_sets[v].rbegin()) {
        ret = std::max(ret, depth[u] - depth[v] + *virtual_sets[v].rbegin());
      } else if (virtual_sets[v].size() >= 2) {
        ret = std::max(ret, depth[u] - depth[v] + *std::prev(std::prev(virtual_sets[v].end())));
      }
    }
    if (dfn[v] < dfn[e]) {
      int val = tree[1].query(dfn[v] + 1, dfn[e], 0, n - 1);
      if (val != -INF) {
        ret = std::max(ret, val - dfn[v] + depth[u] - depth[v]);
      }
    }
    if (dfn[w] < dfn[v]) {
      int val = tree[0].query(dfn[w], dfn[v] - 1, 0, n - 1);
      if (val != -INF) {
        ret = std::max(ret, val + dfn[v] + depth[u] - depth[v]);
      }
    }
    DUMP(v, ret);
    prev_head = header[v];
    v = parent[header[v]];
  }
  return ret;
}

#define ERASE_ONE(set, elem) (set).erase((set).find(elem))

void hld_insert(int u) {
  std::vector<int> stack;
  for (int v = u; v != -1; v = parent[header[v]]) {
    stack.emplace_back(v);
  }
  for (int i = (int)stack.size() - 1; i >= 0; --i) {
    int x = stack[i];
    int h = header[x];
    if (parent[h] != -1) {
      int val = tree[1].query(dfn[h], dfn[last[h]], 0, n - 1);
      if (val != -INF) {
        ERASE_ONE(virtual_sets[parent[h]], val - dfn[h] + 1);
      }
    }
  }
  virtual_sets[u].emplace(0);
  for (int x : stack) {
    int val = *virtual_sets[x].rbegin();
    tree[0].modify(dfn[x], val - dfn[x], 0, n - 1);
    tree[1].modify(dfn[x], val + dfn[x], 0, n - 1);
    int h = header[x];
    if (parent[h] != -1) {
      int val = tree[1].query(dfn[h], dfn[last[h]], 0, n - 1);
      if (val != -INF) {
        virtual_sets[parent[h]].emplace(val - dfn[h] + 1);
      }
    }
  }
}

void hld_remove(int u) {
  std::vector<int> stack;
  for (int v = u; v != -1; v = parent[header[v]]) {
    stack.emplace_back(v);
  }
  for (int i = (int)stack.size() - 1; i >= 0; --i) {
    int x = stack[i];
    int h = header[x];
    if (parent[h] != -1) {
      int val = tree[1].query(dfn[h], dfn[last[h]], 0, n - 1);
      if (val != -INF) {
        ERASE_ONE(virtual_sets[parent[h]], val - dfn[h] + 1);
      }
    }
  }
  ERASE_ONE(virtual_sets[u], 0);
  for (int x : stack) {
    if (!virtual_sets[x].empty()) {
      int val = *virtual_sets[x].rbegin();
      tree[0].modify(dfn[x], val - dfn[x], 0, n - 1);
      tree[1].modify(dfn[x], val + dfn[x], 0, n - 1);
    } else {
      tree[0].modify(dfn[x], -INF, 0, n - 1);
      tree[1].modify(dfn[x], -INF, 0, n - 1);
    }
    int h = header[x];
    if (parent[h] != -1) {
      int val = tree[1].query(dfn[h], dfn[last[h]], 0, n - 1);
      if (val != -INF) {
        virtual_sets[parent[h]].emplace(val - dfn[h] + 1);
      }
    }
  }
}

int main() {
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    scanf("%d%d", &a, &b); --a; --b;
    edges[a].emplace_back(b);
    edges[b].emplace_back(a);
  }
  get_sz(0, -1);
  rebuild(0, -1, 0);
  tree[0].build(0, n - 1);
  tree[1].build(0, n - 1);
  init_jump();
  while (q--) {
    int op;
    scanf("%d", &op);
    if (op == 1) {
      int u, v;
      scanf("%d%d", &u, &v); --u; --v;
      int lca = get_lca(u, v);
      bit.hld_update(u, 1);
      bit.hld_update(v, 1);
      bit.hld_update(lca, -1);
      multiset.emplace(depth[lca], lca);
      hld_insert(lca);
    } else if (op == 2) {
      int u, v;
      scanf("%d%d", &u, &v); --u; --v;
      int lca = get_lca(u, v);
      bit.hld_update(u, -1);
      bit.hld_update(v, -1);
      bit.hld_update(lca, 1);
      ERASE_ONE(multiset, std::make_pair(depth[lca], lca));
      hld_remove(lca);
    } else {
      int d;
      scanf("%d", &d);
      CHECK(!multiset.empty());
      int v = multiset.rbegin()->second;
      int guard = jump(v, d + d);
      if (bit.query(dfn[guard]) != bit.query(dfn[0])) {
        puts("No");
        continue;
      }
      puts(hld_query(v, guard) <= d + d ? "Yes" : "No");
    }
  }
}