#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 120005, K = 20; vector<pair<int, int>> nei[N]; vector<vector<int>> vec[N]; // 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){ vec[u].push_back({!!ic, !!dc, i2, vec[p].back()[3], p, mx, mn}); // inc[u].push_back(!!ic); // des[u].push_back(!!dc); // id[u].push_back(i2); // Par[u].push_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)); vec[u].push_back({1, 1, 0, u, -1, 0, N + N}); // 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(){ 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); string Ans; 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(vec[u].size(), vec[v].size()) and vec[u][j][3] == vec[v][j][3];j++){ int cr = v; if (vec[u][j][4] == cr) cr = u; if (vec[cr][j][0]) ft[vec[cr][j][3]].Add(vec[cr][j][2]); } } else if (t[i] == 'Q'){ int j = 0; while (j + 1 < min(vec[u].size(), vec[v].size()) and vec[u][j+1][3] == vec[v][j+1][3]) j++; if (vec[v][j][1] and vec[u][j][0] and vec[v][j][5] < vec[u][j][6] and max(vec[u][j][5], vec[v][j][5]) < i) Ans += "yes\n";//cout<<"yes\n"; else Ans += "no\n";//cout<<"no\n"; } else{ int ans = 0; for (int j=0;j<vec[u].size();j++){ if (vec[u][j][1] and vec[u][j][5] <= i) ans += ft[vec[u][j][3]].get(vec[u][j][2] + 1, 0) + 1; } Ans += to_string(ans); Ans += '\n'; } } cout<<Ans; }