#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
using Q = const vector<tuple<char, int, int>>&;
void yno(bool b) {
if (b) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
namespace s1 {
bool solve(int n, Q queries) {
if (n > 4000) {
return false;
}
vector<int> arr[n];
for (int i = 0; i < n; i++) {
arr[i] = {i};
}
int cnt[n] {};
for (auto& [c, u, v] : queries) {
if (c == 'S') {
if (sz(arr[v]) > sz(arr[u])) {
swap(arr[u], arr[v]);
}
vector<int> out(sz(arr[u]) + sz(arr[v]));
merge(begin(arr[u]), end(arr[u]), begin(arr[v]), end(arr[v]), out.begin());
arr[u] = out;
swap(out, arr[v]);
for (auto& a : arr[u]) {
cnt[a]++;
}
} else if (c == 'Q') {
if (binary_search(begin(arr[u]), end(arr[u]), v)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
} else {
cout << cnt[u] + 1 << endl;
}
}
return true;
}
} // namespace s1
namespace s2 {
bool solve(int n, Q queries) {
for (auto& [c, u, v] : queries) {
if (c == 'S' && u && v) {
return false;
}
}
vector<int> vals;
int ord[n], oind = 0;
memset(ord, -1, sizeof(ord));
for (auto& [c, u, v] : queries) {
if (c == 'S') {
int x = u;
if (!x) {
x = v;
}
vals.push_back(x);
ord[x] = oind++;
} else if (c == 'Q') {
if (u == v) {
yno(true);
} else if (u == 0) {
yno(ord[v] != -1);
} else if (v == 0) {
yno(ord[u] != -1);
} else {
yno(ord[u] != -1 && ord[v] != -1 && ord[u] > ord[v]);
}
} else {
if (u == 0) {
cout << oind + 1 << endl;
} else if (ord[u] == -1) {
cout << 1 << endl;
} else {
cout << oind - ord[u] + 1 << endl;
}
}
}
return true;
}
} // namespace s2
namespace s3 {
const int maxn = 2e5, logn = 20;
vector<pair<int, int>> graph[maxn];
int t, tin[maxn], tout[maxn], par[maxn], parv[maxn], lift1[logn][maxn], lift2[logn][maxn],
liftv1[logn][maxn], liftv2[logn][maxn];
void dfs(int u, int p = -1) {
tin[u] = t++;
par[u] = lift1[0][u] = lift2[0][u] = p;
for (auto& [v, w] : graph[u]) {
if (v != p) {
parv[v] = liftv1[0][v] = liftv2[0][v] = w;
dfs(v, u);
}
}
tout[u] = t++;
}
bool anc(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
template <typename T>
int blift(int u, int v, int lift[logn][maxn], int liftv[logn][maxn], const T& t) {
if (anc(u, v)) {
return u;
}
int prev = -1;
for (int i = logn - 1; i >= 0; i--) {
int p = lift[i][u];
if (p != -1 && !anc(p, v)) {
if (prev != -1 && !t(prev, parv[u])) {
return -1;
}
prev = liftv[i][u];
u = p;
}
}
if (lift[0][u] == -1) {
return -1;
}
if (prev != -1 && !t(prev, parv[u])) {
return -1;
}
return u;
}
bool solve(int n, Q queries) {
for (auto& [c, _u, _v] : queries) {
if (c == 'C') {
return false;
}
}
int ct = 0;
for (auto& [c, u, v] : queries) {
if (c == 'S') {
graph[u].emplace_back(v, ct);
graph[v].emplace_back(u, ct);
ct++;
}
}
dfs(0);
// 1 - increasing upwards
// 2 - decreasing upwards
for (int i = 1; i < logn; i++) {
for (int j = 0; j < n; j++) {
{
int p = lift1[i - 1][j];
if (p != -1 && liftv1[i - 1][j] < parv[p]) {
lift1[i][j] = lift1[i - 1][p];
liftv1[i][j] = liftv1[i - 1][p];
} else {
lift1[i][j] = -1;
}
}
{
int p = lift2[i - 1][j];
if (p != -1 && liftv2[i - 1][j] > parv[p]) {
lift2[i][j] = lift2[i - 1][p];
liftv2[i][j] = liftv2[i - 1][p];
} else {
lift2[i][j] = -1;
}
}
}
}
ct = -1;
for (auto [c, u, v] : queries) {
if (c == 'S') {
ct++;
} else {
swap(u, v);
if (u == v) {
yno(true);
} else {
int cu = blift(u, v, lift1, liftv1, [&](int a, int b) -> bool {
return a < b;
});
int cv = blift(v, u, lift2, liftv2, [&](int a, int b) -> bool {
return b < a;
});
if (cu != -1 && cv != -1) {
dbg(u, v, cu, cv, par[cu], par[cv]);
int lca = anc(u, v) ? u : par[cu];
dbg(lca);
if (lca != (anc(v, u) ? v : par[cv])) {
yno(false);
continue;
}
assert(lca == (anc(v, u) ? v : par[cv]));
if (anc(u, v)) {
yno(parv[v] <= ct);
} else if (anc(v, u)) {
yno(parv[cu] <= ct);
} else {
yno(parv[cu] < parv[cv] && parv[v] <= ct);
}
} else {
yno(false);
}
}
}
}
return true;
}
} // namespace s3
void solve() {
int n, q;
cin >> n >> q;
vector<tuple<char, int, int>> queries(n + q - 1);
for (auto& [c, u, v] : queries) {
cin >> c;
if (c != 'C') {
cin >> u >> v;
u--;
v--;
} else {
cin >> u;
u--;
}
}
s3::solve(n, queries) || s2::solve(n, queries) || s1::solve(n, queries);
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin.exceptions(ios::failbit);
solve();
}
