#include <bits/stdc++.h>
#define maxn 120005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
const int INF = 1'000'000'000;
int n, k;
vector<ii> adj[maxn];
struct query {
char type; int u, v;
query() {}
} queries[maxn+maxn];
int pe[maxn], d[maxn], f[17][maxn], g[17][maxn], nho[maxn], par[maxn], sz[maxn], tsz = 0, start[maxn], stop[maxn], id = 0;
vector<int> lis[maxn];
int ASC[maxn], DESC[maxn];
int isAncestor(int u, int v) {
return start[u] <= start[v] && stop[v] <= stop[u];
}
int jump(int x, int k) {
for (int i = 0; i < 17; i++) if (k>>i&1) x = f[i][x];
return x;
}
int LCA(int u, int v) {
if (d[u] > d[v]) swap(u, v);
if (d[u] < d[v]) v = jump(v, d[v]-d[u]);
if (u == v) return u;
for (int i = 16; i >= 0; i--)
if (f[i][u] != f[i][v]) {
u = f[i][u];
v = f[i][v];
}
return f[0][u];
}
void pfs(int u, int dad) {
start[u] = ++id;
f[0][u] = dad; g[0][u] = pe[u];
for (int i = 1; i < 17; i++) {
f[i][u] = f[i-1][f[i-1][u]];
g[i][u] = max(g[i-1][u], g[i-1][f[i-1][u]]);
}
ASC[u] = (pe[u] < pe[dad] ? ASC[dad] : dad);
DESC[u] = (pe[u] > pe[dad] ? DESC[dad] : dad);
for (auto [v, l] : adj[u])
if (v != dad) {
pe[v] = l;
d[v] = d[u]+1;
pfs(v, u);
}
stop[u] = id;
}
int ASCENSION(int u, int w) {
return d[ASC[u]] <= d[w];
}
int DECENSION(int u, int w) {
return d[DESC[u]] <= d[w];
}
int MAXIMUS(int u, int v, int w, int TIME) {
int k, ans = 0;
k = d[u]-d[w];
for (int i = 0; i < 17; i++) if (k>>i&1) {
ans = max(ans, g[i][u]);
u = f[i][u];
}
k = d[v]-d[w];
for (int i = 0; i < 17; i++) if (k>>i&1) {
ans = max(ans, g[i][v]);
v = f[i][v];
}
return ans < TIME;
}
int possiblePath(int u, int v, int TIME) {
int w = LCA(u, v);
int condition = 1;
condition &= ASCENSION(u, w);
condition &= DECENSION(v, w);
if (w != u && w != v) condition &= (pe[jump(u, d[u]-d[w]-1)] < pe[jump(v, d[v]-d[w]-1)]);
condition &= MAXIMUS(u, v, w, TIME);
return condition;
}
int lastEdge(int u, int v) {
if (isAncestor(v, u)) return pe[jump(u, d[u]-d[v]-1)];
return pe[v];
}
int firstEdge(int u, int v) {
if (isAncestor(u, v)) return pe[jump(v, d[v]-d[u]-1)];
return pe[u];
}
void queryQ(int u, int v, int TIME) {
cout << (possiblePath(u, v, TIME) ? "yes\n" : "no\n");
}
void resz(int u, int dad) {
++tsz; sz[u] = 1;
for (auto [v, l] : adj[u])
if (!nho[v] && v != dad) {
resz(v, u);
sz[u] += sz[v];
}
}
int findCentroid(int u, int dad) {
for (auto [v, l] : adj[u])
if (v != dad && !nho[v] && sz[v] > tsz/2) return findCentroid(v, u);
return u;
}
void dcp(int u, int r) {
tsz = 0;
resz(u, 0);
int C = findCentroid(u, 0);
nho[C] = 1;
par[C] = r;
for (auto [v, l] : adj[C])
if (!nho[v]) dcp(v, C);
}
struct node {
int val = 0;
node *leftChild = nullptr, *rightChild = nullptr;
node() {}
node(int _val) : val(_val) {}
void extendLeft() {
if (leftChild == nullptr) leftChild = new node;
}
void extendRight() {
if (rightChild == nullptr) rightChild = new node;
}
};
node *st[maxn];
void upd(int u, int d, node *cur, int lo = 1, int hi = n+k-1) {
if (lo == hi) {
cur->val += d;
return;
}
int mid = (lo + hi) >> 1;
if (u <= mid) {
cur->extendLeft();
upd(u, d, cur->leftChild, lo, mid);
} else {
cur->extendRight();
upd(u, d, cur->rightChild, mid+1, hi);
}
cur->val = (cur->leftChild == nullptr ? 0 : cur->leftChild->val)
+ (cur->rightChild == nullptr ? 0 : cur->rightChild->val);
}
int get(int u, int v, node *cur, int lo = 1, int hi = n+k-1) {
if (u <= lo && hi <= v) return cur->val;
int mid = (lo + hi) >> 1;
return ((u <= mid && cur->leftChild != nullptr) ? get(u, v, cur->leftChild, lo, mid) : 0)
+ ((v > mid && cur->rightChild != nullptr) ? get(u, v, cur->rightChild, mid+1, hi) : 0);
}
int ID = 0;
struct pizza {
int x, y, z;
pizza() {}
pizza(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
bool operator < (const pizza &other) const {
return y < other.y;
}
} skibidi[17*maxn];
void init() {
for (int i = 1; i <= n; i++) st[i] = new node(0);
for (int i = 1; i <= n; i++) {
int j = par[i];
while (j) {
if (!possiblePath(j, i, INT_MAX)) {
j = par[j];
continue;
}
skibidi[++ID] = pizza(j, lastEdge(j, i), firstEdge(j, i));
j = par[j];
}
}
sort(skibidi + 1, skibidi + ID + 1);
}
void queryC(int x, int TIME) {
int ans = st[x]->val+1;
for (int y = x; y = par[y];) {
if (!possiblePath(x, y, TIME)) continue;
++ans;
int xd = lastEdge(x, y);
if (xd < n+k-1) ans += get(xd+1, n+k-1, st[y]);
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for (int i = 1; i < n+k; i++) {
cin >> queries[i].type >> queries[i].u;
if (queries[i].type != 'C') cin >> queries[i].v;
if (queries[i].type == 'S') {
adj[queries[i].u].emplace_back(queries[i].v, i);
adj[queries[i].v].emplace_back(queries[i].u, i);
}
}
pfs(1, 0);
dcp(1, 0);
init();
for (int i = 1, it = 1; i < n+k; i++) {
while (it <= ID && skibidi[it].y < i) {
auto [x, y, z] = skibidi[it];
upd(z, 1, st[x]);
++it;
}
if (queries[i].type == 'Q') queryQ(queries[i].v, queries[i].u, i);
else if (queries[i].type == 'C') queryC(queries[i].u, i);
}
}
