可以发现，一条边 \((x,y)\) 的答案，就是 \(x\) 不经过该边可达的点的数量（记作 \(cnt_x\)） \(\times\) \(y\) 不经过该边可达的点的数量（记作 \(cnt_y\)）。
尝试将这个式子转化，若 \(x\) 是 \(y\) 的父亲，那么 \(cnt_x=siz_{root_x}-siz_{y},cnt_y=siz_y\)，其中 \(root_x\) 表示在询问 \((x,y)\) 的时候，结点 \(x\) 的根，\(siz_x\) 表示在树上子树大小。
所以我们实际只需维护每个点在某个当前时段的根，以及其子树大小。
既然最终的结果是森林，我们不妨将最终的森林先建出来，然后再讨论，为了方便，下文讨论的情况均在一棵树上。
考虑对于加边 \((x,y)\)，若 \(x\) 是 \(y\) 的父亲，那么显然，对于 \(x\rightarrow root_x\) 这条链上的所有点，都需要加上 \(siz_y\)，那么我们尝试差分，由于最终需要询问子树大小，所以将 \(b_x+siz_y\)，\(b_{fa_{root_x}}-siz_y\)，最后查询只需查询子树和即可。
由于子树内 \(dfn\) 序连续，所以直接树状数组维护即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') { if(c=='-') flag=-1; c=getchar(); }
while(c>='0'&&c<='9') { sum=sum*10+(c-'0'); c=getchar(); }
return sum*flag;
}
const int N=1e5+10;
int n,q;
int f[N],fa[N],siz[N];
int cnt,dfn[N],l[N],r[N];
vector<int> g[N];
int tr[N];
int pd[N];
struct node {
int opt,x,y;
}s[N];
int lowbit(int n) {
return n&(-n);
}
void modify(int nd,int x) {
if(!nd) return ;
for(int i=nd;i<=n;i+=lowbit(i)) tr[i]+=x;
}
int query(int nd) {
int ans=0;
for(int i=nd;i;i-=lowbit(i)) ans+=tr[i];
return ans;
}
int find(int x) {
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
void add(int x,int y) {
g[x].push_back(y);
}
void dfs(int nd,int fa) {
dfn[nd]=++cnt;
f[nd]=fa;
l[nd]=cnt; r[nd]=cnt;
for(int x:g[nd]) {
if(x==fa) continue;
dfs(x,nd);
l[nd]=min(l[nd],l[x]);
r[nd]=max(r[nd],r[x]);
}
}
int ask(int x) {
return query(r[x])-query(l[x]-1);
}
int main() {
cin>>n>>q;
for(int i=1;i<=q;i++) {
string opt;
cin>>opt>>s[i].x>>s[i].y;
if(opt=="A") {
s[i].opt=1;
add(s[i].x,s[i].y); add(s[i].y,s[i].x);
}
else s[i].opt=2;
}
for(int i=1;i<=n;i++) {
fa[i]=i;
if(!dfn[i]) dfs(i,0);
}
for(int i=1;i<=n;i++) {
modify(dfn[i],1); modify(dfn[f[i]],-1);
}
for(int i=1;i<=q;i++) {
int x=s[i].x,y=s[i].y;
if(f[x]==y) swap(x,y);
if(s[i].opt==1) {
int root=find(x),siz=ask(y);
modify(dfn[x],siz); modify(dfn[f[root]],-siz); fa[y]=x;
}
else {
int root=find(x);
LL ans=(LL)(ask(root)-ask(y))*(LL)ask(y);
cout<<ans<<'\n';
}
}
return 0;
}