#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ar array
using namespace __gnu_pbds;
using namespace std;
using iset = tree<ar<int, 2>, null_type, less<ar<int, 2>>, rb_tree_tag, tree_order_statistics_node_update>;
const int mxN = 120'000;
const int INF = 1e9;
vector<ar<int, 2>> g[mxN];
int cut[mxN], sz[mxN];
int dfs1(int cur, int prv) {
sz[cur] = 1;
for (auto [nxt, t] : g[cur]) {
if (cut[nxt]) continue;
if (nxt == prv) continue;
sz[cur] += dfs1(nxt, cur);
}
return sz[cur];
}
vector<int> kids[mxN];
int find_centroid(int cur, int prv, int total) {
for (auto [nxt, t] : g[cur]) {
if (cut[nxt]) continue;
if (nxt == prv) continue;
if (2*sz[nxt] > total) return find_centroid(nxt, cur, total);
}
// this is centroid
cut[cur] = 1;
if (prv != -1 && !cut[prv])
dfs1(prv, -1);
for (auto [nxt, t] : g[cur]) {
if (cut[nxt]) continue;
kids[cur].push_back(find_centroid(nxt, -1, sz[nxt]));
}
return cur;
}
int clvl[mxN];
vector<int> cent_anc[mxN];
iset branches_start[mxN];
void set_anc(int anc, int cur, int prv) {
cent_anc[cur].push_back(anc);
for (auto [nxt, t] : g[cur]) {
if (cut[nxt]) continue;
if (nxt == prv) continue;
set_anc(anc, nxt, cur);
}
}
gp_hash_table<int, int> out_ws[mxN], in_ws[mxN], path_end[mxN];
void init_reach_out(int root, int bw, int cur, int prv, int w) {
out_ws[root][cur] = bw;
path_end[root][cur] = w;
for (auto [nxt, t] : g[cur]) {
if (cut[nxt]) continue;
if (nxt == prv) continue;
if (t < w) continue;
init_reach_out(root, bw, nxt, cur, t);
}
}
void init_reach_in(int root, int bw, int cur, int prv, int w) {
in_ws[root][cur] = bw;
for (auto [nxt, t] : g[cur]) {
if (cut[nxt]) continue;
if (nxt == prv) continue;
if (t > w) continue;
init_reach_in(root, bw, nxt, cur, t);
}
}
void init_centroid(int cur, int d) {
clvl[cur] = d;
for (int nxt : kids[cur])
init_centroid(nxt, d+1);
cent_anc[cur].push_back(cur);
for (auto [nxt, t] : g[cur]) {
if (cut[nxt]) continue;
set_anc(cur, nxt, -1);
}
cut[cur] = 0;
out_ws[cur][cur] = INF;
in_ws[cur][cur] = -INF;
path_end[cur][cur] = -INF;
for (auto [nxt, t] : g[cur]) {
if (cut[nxt]) continue;
init_reach_out(cur, t, nxt, cur, t);
init_reach_in(cur, t, nxt, cur, t);
}
}
bool qry(int i, int j, int t) {
int ci = 0;
int cj = 0;
while (cent_anc[i][ci] != cent_anc[j][cj]) {
if (clvl[cent_anc[i][ci]] > clvl[cent_anc[j][cj]]) ++ci;
else if (clvl[cent_anc[j][cj]] > clvl[cent_anc[i][ci]]) ++cj;
else ++ci, ++cj;
}
int lca = cent_anc[i][ci];
auto in_it = in_ws[lca].find(j);
auto out_it = out_ws[lca].find(i);
if (in_it == in_ws[lca].end()) return false;
if (out_it == out_ws[lca].end()) return false;
if (in_it->second > t) return false;
if (in_it->second > out_it->second) return false;
if (path_end[lca][i] > t) return false;
return true;
}
int count_reachable(int i, int hi) {
int ans = 0;
for (int root : cent_anc[i]) {
auto reach_it = in_ws[root].find(i);
if (reach_it == in_ws[root].end()) continue;
int lo = reach_it->second;
if (lo > hi) continue;
++ans;
int here = (int)branches_start[root].size();
if (here) {
if (lo >= 0) here -= (int)branches_start[root].order_of_key({lo, INF});
if (here < 0) here = 0;
}
ans += here;
}
return ans;
}
int brute_reachable(int i, int t, int n) {
int ans = 0;
for (int j = 0; j < n; ++j)
ans += qry(j, i, t);
return ans;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int n, q; cin >> n >> q;
vector<ar<int, 3>> qs;
vector<ar<int, 2>> cs;
for (int t = 0; t < n+q-1; ++t) {
char c; cin >> c;
if (c == 'S') {
int i, j; cin >> i >> j; --i, --j;
g[i].push_back({j, t});
g[j].push_back({i, t});
} else if (c == 'Q') {
int i, j; cin >> i >> j; --i, --j;
qs.push_back({t, i, j});
} else if (c == 'C') {
int i; cin >> i; --i;
cs.push_back({t, i});
} else assert(0);
}
dfs1(0, -1);
int root = find_centroid(0, -1, sz[0]);
for (int i = 0; i < n; ++i)
assert(cut[i]);
init_centroid(root, 0);
for (int i = 0; i < n; ++i)
assert(!cut[i]);
vector<pair<int, string>> ans; ans.reserve(q);
for (auto [t, i, j] : qs)
ans.push_back({t, qry(i, j, t)?"yes":"no"});
vector<ar<int, 4>> upd_q;
for (int i = 0; i < n; ++i) {
for (int rt : cent_anc[i]) {
if (i == rt) continue;
auto out_it = out_ws[rt].find(i);
if (out_it == out_ws[rt].end()) continue;
int w_start = out_it->second;
int w_end = path_end[rt][i];
upd_q.push_back({w_end, w_start, rt, i});
}
}
int upd_i = 0;
sort(upd_q.begin(), upd_q.end());
for (auto [t, i] : cs) {
while (upd_i < (int)upd_q.size() && upd_q[upd_i][0] <= t) {
auto [ut, w, rt, nd] = upd_q[upd_i++];
branches_start[rt].insert({w, nd});
}
ans.push_back({t, to_string(count_reachable(i, t))});
}
sort(ans.begin(), ans.end());
for (auto &[t, s] : ans)
cout << s << '\n';
}
