#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
#define SZ(x) (int) x.size()
const int N = 120'005, LOG = 18;
vector<array<int, 3>> adj[N];
//0: increasing, 1: decreasing, {ancestor, last weight}
array<int, 3> bl[N][LOG][2];
int st[N], en[N], curt;
void dfs(int i, int par, int part) {
bl[i][0][0] = {par, part, part};
bl[i][0][1] = {par, part, part};
for (int j = 1; j < LOG; j++) {
{
bl[i][j][0] = bl[i][j - 1][0];
auto [lst, lstt, mx] = bl[i][j][0];
if (lstt <= bl[lst][0][0][1]) {
bl[i][j][0] = bl[lst][j - 1][0];
bl[i][j][0][2] = max(bl[i][j][0][2], mx);
}
}
{
bl[i][j][1] = bl[i][j - 1][1];
auto [lst, lstt, mx] = bl[i][j][1];
if (lstt >= bl[lst][0][1][1]) {
bl[i][j][1] = bl[lst][j - 1][1];
bl[i][j][1][2] = max(bl[i][j][1][2], mx);
}
}
}
st[i] = curt++;
for (auto [nxt, t, nxtidx] : adj[i]) {
if (nxt == par) continue;
dfs(nxt, i, t);
}
en[i] = curt;
}
bool isanc(int l, int b) {
if (st[l] <= st[b] && en[b] <= en[l]) {
return 1;
}
return 0;
}
array<int, 2> check(int t, int a, int b) {
int mx = -1e9, high = bl[a][LOG - 1][t][0];
if (!isanc(high, b)) {
return {int(1e9), 0};
}
if (a == high || isanc(a, b)) {
return {int(-1e9), (t == 1? 1 : -1) * int(1e9)};
}
for (int j = LOG - 1; j >= 0; j--) {
if (!isanc(bl[a][j][t][0], b)) {
mx = max(mx, bl[a][j][t][2]);
a = bl[a][j][t][0];
}
}
return {max(mx, bl[a][0][t][2]), bl[a][0][t][1]};
}
vector<int> dp[N];
int lst;
int solve(int i, int par) {
if (~dp[i][par]) return dp[i][par];
int j = (par == SZ(adj[i])? 0 : par + 1);
dp[i][par] = 1;
if (j < SZ(adj[i])) {
if (adj[i][j][1] > lst) return dp[i][par];
dp[i][par] += solve(adj[i][j][0], adj[i][j][2]) + solve(i, j) - 1;
}
return dp[i][par];
}
bool checkpath(int a, int b, int t, bool x) {
array<int, 2> l = check(x, a, b), r = check(!x, b, a);
if (l[0] <= t && r[0] <= t && (l[1] == r[1] || (x ^ (l[1] < r[1]))) ) {
return 1;
} else {
return 0;
}
}
const int B = 500;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
auto S = chrono::steady_clock::now().time_since_epoch().count();
int n, q;
cin >> n >> q;
q += n - 1;
pair<char, vector<int>> v[q];
for (int i = 0; i < q; i++) {
cin >> v[i].first;
if (v[i].first == 'S') {
int a, b;
cin >> a >> b;
int x = adj[b].size(), y = adj[a].size();
adj[a].push_back({b, i, x});
adj[b].push_back({a, i, y});
v[i].second = {a, b};
} else if (v[i].first == 'Q') {
int a, b;
cin >> a >> b;
v[i].second = {a, b};
} else {
int a;
cin >> a;
v[i].second = {a};
}
}
dfs(1, 1, 0);
for (int i = 1; i <= n; i++) {
dp[i].resize(adj[i].size() + 1);
for (int j = 0; j <= SZ(adj[i]); j++) {
dp[i][j] = -1;
}
}
vector<array<int, 3>> upd;
lst = -1;
ll s = 0;
for (int i = 0; i < q; i++) {
if (upd.size() == B) {
lst = i - 1;
upd.clear();
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= SZ(adj[j]); k++) {
dp[j][k] = -1;
}
}
}
if (v[i].first == 'S') {
int a = v[i].second[0], b = v[i].second[1];
if (isanc(b, a)) swap(a, b);
upd.push_back({a, b, i});
} else if (v[i].first == 'Q') {
int a = v[i].second[0], b = v[i].second[1];
#ifdef MINA
s += (checkpath(a, b, i, 1));
#else
cout << (checkpath(a, b, i, 1)? "yes\n" : "no\n");
#endif
} else {
int x = v[i].second[0];
int ans = solve(x, adj[x].size());
for (auto [a, b, t] : upd) {
if (isanc(b, x)) {
array<int, 2> val = check(0, x, b);
ans += val[0] <= t - 1;
} else if (isanc(a, x)) {
array<int, 2> val = check(0, x, a);
ans += val[0] <= t - 1;
} else {
ans += checkpath(x, a, t - 1, 0);
}
}
#ifdef MINA
s += ans;
#else
cout << ans << '\n';
#endif
}
}
#ifdef MINA
cout << s << '\n';
auto E = chrono::steady_clock::now().time_since_epoch().count();
cout << (E - S) / 1e9 << "s\n";
#endif
return 0;
}
