#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 120005, K = 20; vector<pair<int, int>> nei[N]; vector<int> Par[N], pr[N], id[N], inc[N], des[N], Mx[N], Mn[N]; int ch[N], dead[N], a[N<<1], b[N<<1]; 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[p]) 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 u, int p, int ic, int dc, int i2, int mx, int mn){ inc[u].push_back(!!ic); des[u].push_back(!!dc); id[u].push_back(i2); Par[u].push_back(Par[p].back()); pr[u].push_back(p); Mx[u].push_back(mx); Mn[u].push_back(mn); 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, u, ic1, dc1, i2, max(mx, j), min(mn, j)); } } void decomp(int u, 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)); inc[u].push_back(1); des[u].push_back(1); id[u].push_back(0); Par[u].push_back(u); pr[u].push_back(-1); Mx[u].push_back(0); Mn[u].push_back(N + N); for (auto [j, i] : vc) dfsColor(i, u, j, j, ++cid, j, j); ft[u].init(cid); dead[u] = 1; for (auto [j, i] : vc) decomp(i); } int main(){ 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(Par[u].size(), Par[v].size()) 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(Par[u].size(), Par[v].size()) 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 Mx[u][j] < i) cout<<"yes\n"; else cout<<"no\n"; } else{ int Ans = 0; for (int i=0;i<Par[u].size();i++) Ans += des[u][i] * (ft[Par[u][i]].get(id[u][i] + 1, 0) + 1); cout<<Ans<<'\n'; } } }