#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 120005, K = 20; vector<pair<int, int>> nei[N]; int pr[N][K], id[N][K], inc[N][K], des[N][K], Mx[N][K], Mn[N][K], Par[N][K]; int ch[N], dead[N], a[N<<1], b[N<<1], Sz[N]; char t[N<<1]; struct fwTree{ vector<int> ds; int n; void init(int sz){ n = sz; ds.resize(n + 1, 0); } void Add(int i){ for (; i; i -= i & -i) ds[i]++; } int get(int i, int ans){ for (; i <= n; i += i & -i) ans += ds[i]; return ans; } } ft[N]; void dfs1(int u, int p){ ch[u] = 1; for (auto [i, j] : nei[u]) if (i != p and !dead[i]) dfs1(i, u), ch[u] += ch[i]; } int cent(int u, int p, int sz){ for (auto [i, j] : nei[u]){ if (i != p and !dead[i] and ch[i] * 2 >= sz) return cent(i, u, sz); } return u; } void dfsColor(int I, int u, int p, int ic, int dc, int i2, int mx, int mn){ Par[u][I] = Par[p][I]; inc[u][I] = !!ic; des[u][I] = !!dc; id[u][I] = i2; pr[u][I] = p; Mx[u][I] = mx; Mn[u][I] = mn; Sz[u]++; for (auto [i, j] : nei[u]){ if (dead[i] or i == p) continue; int ic1 = ((j > ic and ic != 0) ? j : 0), dc1 = (j < dc ? j : 0); dfsColor(I, i, u, ic1, dc1, i2, max(mx, j), min(mn, j)); } } void decomp(int u, int I = 0, int cid = 0){ dfs1(u, -1); u = cent(u, -1, ch[u]); vector<pair<int, int>> vc; for (auto [i, j] : nei[u]){ if (!dead[i]) vc.push_back({j, i}); } sort(begin(vc), end(vc)); Par[u][I] = u; inc[u][I] = 1; des[u][I] = 1; id[u][I] = 0; pr[u][I] = -1; Mx[u][I] = 0; Mn[u][I] = N+N; Sz[u]++; for (auto [j, i] : vc) dfsColor(I, i, u, j, j, ++cid, j, j); ft[u].init(cid); dead[u] = 1; for (auto [j, i] : vc) decomp(i, I + 1); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin>>n>>k, k--; for (int i=1;i<=n+k;i++){ cin>>t[i]>>a[i]; if (t[i] != 'C') cin>>b[i]; if (t[i] == 'S'){ nei[a[i]].push_back({b[i], i}); nei[b[i]].push_back({a[i], i}); } } decomp(1); for (int i=1;i<=n+k;i++){ int u = a[i], v = b[i]; if (t[i] == 'S'){ for (int j=0;j < min(Sz[u], Sz[v]) and Par[u][j] == Par[v][j];j++){ int cr = v; if (pr[u][j] == cr) cr = u; if (inc[cr][j]) ft[Par[cr][j]].Add(id[cr][j]); } } else if (t[i] == 'Q'){ int j = 0; while (j + 1 < min(Sz[u], Sz[v]) and Par[u][j+1] == Par[v][j+1]) j++; if (des[v][j] and inc[u][j] and Mx[v][j] < Mn[u][j] and max(Mx[u][j], Mx[v][j]) < i) cout<<"yes\n"; else cout<<"no\n"; } else{ int Ans = 0; for (int j=0;j<Sz[u];j++){ if (des[u][j] and Mx[u][j] <= i) Ans += ft[Par[u][j]].get(id[u][j] + 1, 0) + 1; } cout<<Ans<<'\n'; } } }