#ifndef LOCAL #pragma GCC Optimize("O3,Ofast,unroll-loops") #pragma GCC Target("bmi,bmi2,avx,avx2") #endif #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define int ll #define f first #define s second #define mp make_pair #define pb push_back #define pii pair<int, int> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin() (x).rend() #ifndef LOCAL #define endl "\n" #endif mt19937 rnd(11); struct F { vector<int> t; F(int n) { t.assign(n, 0); } }; void solve() { int n, q; cin >> n >> q; q += n - 1; vector<pii> quests(q); vector<pii> edges(n - 1); vector<vector<pii>> graph(n); int ind = 0; for (int i = 0; i < q; ++i) { char c; cin >> c; if (c == 'S') { int a, b; cin >> a >> b; --a; --b; edges[ind] = mp(a, b); graph[a].pb(mp(b, ind)); graph[b].pb(mp(a, ind++)); quests[i] = mp(-1, -1); } else if (c == 'Q') { int a, b; cin >> a >> b; --a; --b; quests[i] = mp(a, b); } else { int a; cin >> a; --a; quests[i] = mp(a, 1e9); } } vector<int> sz(n); vector<int> lvl(n, -1); vector<vector<int>> CP(20, vector<int>(n, -1)), CI(20, vector<int>(n)), CD(20, vector<int>(n)), CF(20, vector<int>(n)), CL(20, vector<int>(n)); int l = 0; auto calc_sz = [&](int v, int prev, auto &&self) -> void { sz[v] = 1; for (auto &u : graph[v]) { if (lvl[u.f] == -1 && u.f != prev) { self(u.f, v, self); sz[v] += sz[u.f]; } } }; int tsz = 0; auto find_center = [&](int v, int prev, auto &&self) -> int { for (auto &u : graph[v]) { if (lvl[u.f] == -1 && u.f != prev && sz[u.f] * 2 > tsz) { return self(u.f, v, self); } } return v; }; auto dfs = [&](int v, int prev, int center, bool i, bool d, int fst, int lst, auto &&self) -> void { CI[l][v] = i; CD[l][v] = d; CP[l][v] = center; CF[l][v] = fst; CL[l][v] = lst; for (auto &u : graph[v]) { if (lvl[u.f] == -1 && u.f != prev) { self(u.f, v, center, i&&(lst < u.s), d&&(lst > u.s), fst, u.s, self); } } }; vector<vector<int>> smaller(n); for (; l < 20; ++l) { sz.assign(n, 0); for (int i = 0; i < n; ++i) { if (lvl[i] == -1 && sz[i] == 0) { calc_sz(i, i, calc_sz); tsz = sz[i]; int center = find_center(i, i, find_center); smaller[center].pb(n); lvl[center] = l; for (auto &u : graph[center]) { if (lvl[u.f] == -1) { smaller[center].pb(u.s); dfs(u.f, center, center, true, true, u.s, u.s, dfs); } } sort(all(smaller[center])); } } } vector<vector<int>> F(n); for (int i = 0; i < n; ++i) { F[i].resize(smaller[i].size()); } auto upd = [&](int v, int x) { int i = smaller[v].end() - lower_bound(all(smaller[v]), x) - 1; for (; i < F[v].size(); i = (i|(i + 1))) { F[v][i] += 1; } }; auto get = [&](int v, int x) { int r = smaller[v].end() - upper_bound(all(smaller[v]), x) - 1; int ans = 0; for (; r >= 0; r = (r&(r + 1)) - 1) { ans += F[v][r]; } return ans; }; ind = 0; for (int i = 0; i < n; ++i) { upd(i, n); } for (auto &x : quests) { if (x.f == -1) { auto upd1 = [&](int v, int x) { for (int i = lvl[v] - 1; i >= 0; --i) { if (CL[i][v] == x && CI[i][v]) { upd(CP[i][v], CF[i][v]); } } }; upd1(edges[ind].f, ind); upd1(edges[ind].s, ind); ++ind; continue; } if (x.s == 1e9) { int ans = get(x.f, -1); for (int i = lvl[x.f] - 1; i >= 0; --i) { if (CD[i][x.f] && CF[i][x.f] < ind) { ans += get(CP[i][x.f], CF[i][x.f]); } } cout << ans << endl; } else { bool ans = (x.f == x.s); for (int i = 19; i >= 0; --i) { if (CP[i][x.f] == x.s){ if (CI[i][x.f] && CL[i][x.f] < ind) { ans = true; } break; } if (CP[i][x.s] == x.f) { if (CD[i][x.s] && CF[i][x.s] < ind) { ans = true; } break; } if (CP[i][x.f] == CP[i][x.s] && CP[i][x.f] != -1) { if (CI[i][x.f] && CD[i][x.s] && CF[i][x.s] < CF[i][x.f] && CL[i][x.f] < ind) { ans = true; } break; } } if (ans) { cout << "yes" << endl; } else { cout << "no" << endl; } } } } signed main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #else ios::sync_with_stdio(false); cin.tie(0); #endif int t = 1; // cin >> t; while (t--) { solve(); } }