#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()
const int MAXN = 12e4+10;
vvi adj(MAXN); vi depth(MAXN);
namespace DSU {
vi par(MAXN), sz(MAXN);
void init(){
for(int x = 0; x < MAXN; x++)
par[x] = x, sz[x] = 1;
}
int parent(int x){
if(par[x] == x) return x;
return par[x] = parent(par[x]);
}
void merge(int x, int y){
x = parent(x), y = parent(y);
if(x == y) return;
par[x] = y; sz[y] += sz[x];
}
};
namespace LCA {
int timer = 0;
vi tin(MAXN), tout(MAXN);
vvi par(MAXN, vi(20));
void dfs(int u, int p, int h){
depth[u] = h;
par[u][0] = p;
for(int i = 1; i < 20; i++)
par[u][i] = par[par[u][i-1]][i-1];
tin[u] = timer++;
for(auto v : adj[u])
if(v != p) dfs(v, u, h+1);
tout[u] = timer-1;
}
// Is u an ancestor of v?
bool isAncestor(int u, int v){
return tin[u] <= tin[v] and
tout[v] <= tout[u];
}
int query(int u, int v){
if(isAncestor(u, v)) return u;
if(isAncestor(v, u)) return v;
for(int i = 19; i >= 0; i--)
if(!isAncestor(par[u][i], v))
u = par[u][i];
return par[u][0];
}
int query1(int u, int v){
for(int i = 19; i >= 0; i--)
if(!isAncestor(par[v][i], u))
v = par[v][i];
return v;
}
void init(){
dfs(0, 0, 1);
}
};
namespace BIT {
vi arr(MAXN);
void add(int x, int val){ x++;
for(; x < MAXN; x += x&(-x))
arr[x] += val;
}
int query(int x){ x++;
int ans = 0;
for(; x > 0; x -= x&(-x))
ans += arr[x];
return ans;
}
};
namespace CD {
unordered_set<int> pres;
vi par(MAXN), cnt(MAXN);
int dfs(int u, int p){
cnt[u] = 1;
for(auto v : adj[u])
if(v != p and !pres.count(v))
cnt[u] += dfs(v, u);
return cnt[u];
}
int dfs(int u, int p, int sz){
for(auto v : adj[u])
if(v != p and !pres.count(v))
if(cnt[v] > sz/2) return dfs(v, u, sz);
return u;
}
void build(int u, int p){
int sz = dfs(u,u), ct = dfs(u,u,sz);
par[ct] = p; pres.insert(ct);
for(auto v : adj[ct])
if(!pres.count(v)) build(v, ct);
}
void init(){
build(0, -1);
}
};
bool inc(int u, int v){
int p = LCA::query1(u, v);
auto f = BIT::query(LCA::tin[v])-BIT::query(LCA::tin[p]);
if(f == depth[v]-depth[p]) return true;
return false;
}
bool dec(int u, int v){
int p = LCA::query1(u, v);
auto f = BIT::query(LCA::tin[v])-BIT::query(LCA::tin[p]);
if(f == 0) return true;
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, K; cin >> N >> K;
vector<array<int, 3>> Q(N+K-1);
for(int x = 0; x < N+K-1; x++){
char c; cin >> c;
if(c == 'S'){
int u, v; cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
Q[x] = {0, u, v};
}else if(c == 'Q'){
int u, d; cin >> u >> d;
u--, d--;
Q[x] = {1, d, u};
}else{
int d; cin >> d;
Q[x] = {2, --d, d};
}
}
LCA::init(); DSU::init(); CD::init();
vi isConnected(N);
auto path_exists = [&](int u, int v)->bool{
if(DSU::parent(u) != DSU::parent(v))
return false;
int p = LCA::query(u, v);
if(p == u){
if(inc(u, v)) return true;
}else if(p == v){
if(dec(v, u)) return true;
}else{
int p1 = LCA::query1(p, u), p2 = LCA::query1(p, v);
if(dec(p, u) and inc(p, v) and isConnected[p1] < isConnected[p2])
return true;
}
return false;
};
ordered_set jp[N]; set<ii> mc;
auto uupp = [&](int u){
for(int p = CD::par[u]; p != -1; p = CD::par[p]){
if(!path_exists(p, u)) continue;
if(mc.count({u, p})) continue;
mc.insert({u, p});
int p1;
if(LCA::query(p, u) == p){
p1 = LCA::query1(p, u);
}else p1 = p;
jp[p].insert(isConnected[p1]);
}
};
for(uint x = 0; x < Q.size(); x++){
if(Q[x][0] == 0){
int u = Q[x][1], v = Q[x][2];
if(depth[u] > depth[v]) swap(u, v);
if(isConnected[u])
BIT::add(LCA::tin[v], 1),
BIT::add(LCA::tout[v]+1, -1);
DSU::merge(u, v);
isConnected[v] = x+1;
uupp(u); uupp(v);
}else if(Q[x][0] == 1){
int u = Q[x][1], v = Q[x][2];
if(path_exists(u, v)) cout << "yes\n";
else cout << "no\n";
}else{
int u = Q[x][1], ans = 0;
for(int p = u; p != -1; p = CD::par[p]){
if(p != u and !path_exists(u, p)) continue;
ans++;
if(p == u){
ans += jp[u].size();
}else if(LCA::query(u, p) == p){
int p1 = LCA::query1(p, u);
ans += jp[p].size()-jp[p].order_of_key(isConnected[p1]+1);
} else{
ans += jp[p].size()-jp[p].order_of_key(isConnected[p]+1);
}
}
// int ans1 = 0;
// for(int v = 0; v < N; v++)
// if(v == u or path_exists(u, v)) ans1++;
// assert(ans1 == ans);
cout << ans << "\n";
}
}
return 0;
}
/*
5 2
S 1 2
S 4 5
S 3 4
C 2
S 2 3
C 2
*/
