# 【WA想定】平方分割もどき。次数 > B=floor(sqrt(2M)) の頂点を heavy とし、 # - heavy は隣接頂点に ca/cc を push しない(A(x) = 軽い隣接からの ca_l[x] + heavy 隣接を数える) # - heavy h には SWA[h] = Σ_{b∈N(h), S_b=W} A(b), SWC[h] = Σ C(b) を持たせる # SWA/SWC を「隣接 b が W になる/やめる」ときしか更新せず、 # b の A(b)/C(b) が変わったとき(2ホップ先の変化)の更新を忘れている。 # サンプルは heavy 頂点が存在しないので通ってしまう。 import sys def main(): d=sys.stdin.buffer.read().split();n,m=int(d[0]),int(d[1]);s=list(d[2].decode());p=3 adj=[[] for _ in range(n)] for _ in range(m): u,v=int(d[p])-1,int(d[p+1])-1;p+=2;adj[u].append(v);adj[v].append(u) B=int((2*m)**0.5) heavy=[len(adj[v])>B for v in range(n)] hadj=[[u for u in adj[v] if heavy[u]] for v in range(n)] ca=[0]*n;cc=[0]*n for v in range(n): if heavy[v]: continue if s[v]=='A': for u in adj[v]: ca[u]+=1 elif s[v]=='C': for u in adj[v]: cc[u]+=1 def A(x): return ca[x]+sum(1 for h in hadj[x] if s[h]=='A') def C(x): return cc[x]+sum(1 for h in hadj[x] if s[h]=='C') SWA=[0]*n;SWC=[0]*n for h in range(n): if heavy[h]: for b in adj[h]: if s[b]=='W': SWA[h]+=A(b);SWC[h]+=C(b) ans=sum(A(b)*C(b) for b in range(n) if s[b]=='W') q=int(d[p]);p+=1;out=[] for _ in range(q): v=int(d[p])-1;x=d[p+1].decode();p+=2;o=s[v] if o!=x: if o=='W': a,c=A(v),C(v);ans-=a*c for h in hadj[v]: SWA[h]-=a;SWC[h]-=c elif o=='A': if heavy[v]: ans-=SWC[v] else: for b in adj[v]: if s[b]=='W': ans-=C(b) ca[b]-=1 elif o=='C': if heavy[v]: ans-=SWA[v] else: for b in adj[v]: if s[b]=='W': ans-=A(b) cc[b]-=1 s[v]=x if x=='W': a,c=A(v),C(v);ans+=a*c for h in hadj[v]: SWA[h]+=a;SWC[h]+=c elif x=='A': if heavy[v]: ans+=SWC[v] else: for b in adj[v]: if s[b]=='W': ans+=C(b) ca[b]+=1 elif x=='C': if heavy[v]: ans+=SWA[v] else: for b in adj[v]: if s[b]=='W': ans+=A(b) cc[b]+=1 out.append(ans) print(*out,sep='\n') main()