// https://github.com/potato167/po167_library #include #include using namespace std; using ll=long long; const ll ILL=2167167167167167167; const int INF=2100000000; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using pq_ = priority_queue, greater>; template int LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template int UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(b bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;} template T square(T a){return a * a;} void solve(); // DEAR MYSTERIES / TOMOO int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; rep(i, 0, t) solve(); } void solve(){ int N, M; cin >> N >> M; string S; cin >> S; vector> G(N); rep(i, 0, M) { int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); G[b].push_back(a); } vector RA(N), RC(N); int Q; cin >> Q; vector V(Q); vector C(Q); rep(i, 0, Q) { cin >> V[i] >> C[i]; V[i]--; } const int B = 700; vector sp, sp_ind(N); ll ans = 0; vector Z(B, vector(B)); vector> spG(N); vector WA(N), WC(N); auto f = [&](int ind) -> ll { if (S[ind] == 'W') { return RA[ind] * RC[ind]; } if (S[ind] == 'A') { ll res = WC[ind]; rep(i, 0, sp.size()) if (S[sp[i]] == 'C') { res += Z[sp_ind[ind]][i]; } for (auto x : spG[ind]) if (S[x] == 'W') { res += RC[x]; } return res; } if (S[ind] == 'C') { ll res = WA[ind]; rep(i, 0, sp.size()) if (S[sp[i]] == 'A') { res += Z[sp_ind[ind]][i]; } for (auto x : spG[ind]) if (S[x] == 'W') { res += RA[x]; } return res; } return 0; }; rep(rp, 0, Q) { if (rp % B == 0) { sp.clear(); ans = 0; rep(i, 0, B) rep(j, 0, B) Z[i][j] = 0; rep(i, 0, N) { spG[i].clear(); RA[i] = 0, RC[i] = 0, WA[i] = 0, WC[i] = 0; } int r = min(Q, rp + B); set s; rep(i, 0, N) sp_ind[i] = -1; rep(i, rp, r) s.insert(V[i]); for (auto x : s) { sp_ind[x] = sp.size(); sp.push_back(x); } rep(i, 0, N) { RA[i] = 0, RC[i] = 0; for (auto x : G[i]) { if (S[x] == 'A') RA[i]++; if (S[x] == 'C') RC[i]++; if (sp_ind[i] != -1 && sp_ind[x] != -1) { spG[i].push_back(x); } } if (S[i] == 'W') { if (sp_ind[i] == -1) { int wa = 0, wc = 0; for (auto x : G[i]) if (sp_ind[x] == -1) { if (S[x] == 'A') wa++; if (S[x] == 'C') wc++; } for (auto x : G[i]) if (sp_ind[x] != -1) { WA[x] += wa; WC[x] += wc; } } ans += RA[i] * RC[i]; if (sp_ind[i] == -1) { vector a; for (auto x : G[i]) if (sp_ind[x] != -1) { a.push_back(sp_ind[x]); } for (auto x : a) for (auto y : a) Z[x][y]++; } } } } ans -= f(V[rp]); // upd { for (auto x : spG[V[rp]]) { if (S[V[rp]] == 'A') { RA[x]--; } if (S[V[rp]] == 'C') { RC[x]--; } if (C[rp] == 'A') { RA[x]++; } if (C[rp] == 'C') { RC[x]++; } } } S[V[rp]] = C[rp]; ans += f(V[rp]); cout << ans << "\n"; } } /* * 各頂点ごとに、隣接 A, C, WA, WC * を管理する * これだとTLEなので、平方分割的なことをして、短縮したい * クエリ平方分割を考える * B個以外のパスを全て列挙する * ?W?は、事前に有向グラフをはることで、O(B)で処理できる? * それ以外もよしなに? * wの場合は、単純に全部見ればいい * ? = aで * ?wcは事前計算でもとまる * ??は ? 周りのa,cを管理しておけばok * 固定 WA, WCも管理しないと... * O(QB + NQ /B) */