三元环计数，于是考虑暴力。答案显然为每个点的入度 \(\times\) 出度和，每次修改一个点的时候，遍历所有的入边，将其改为出边，更新答案，一次更新的复杂度是 \(\mathcal{O}(入度)\) 的。
不妨设 \(n,m,q\) 同阶，下面证明其复杂度为 \(\mathcal{O}(n\sqrt n)\)：
在初始状态时，设入度 \(\leq \sqrt{2m}\) 的点集为 \(A\)，设入度 \(>\sqrt{2m}\) 的点集为 \(B\)，定义一个点的势能为入度，一次操作所带来的复杂度即为一个点的势能。
- 操作 \(A\) 中的点，释放 \(\leq \sqrt{2m}\) 的势能，给 \(B\) 带来的势能 \(\leq \sqrt{2m}\)；
- 操作 \(B\) 中的点，释放 \(B\) 给其的势能，由于 \(|B|<\sqrt {2m}\)，所以这部分 \(\leq \sqrt 2m\)；
- 操作 \(B\) 中的点，释放 \(A\) 给其的势能，根据 1. 中的分析，其总量 \(\leq q\sqrt {2m}\)．
综上所述，总的时间复杂度为 \(\mathcal{O}(n+m+q\sqrt n)\)．
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> vi;
typedef std::vector<pii> vpii;
typedef std::vector<ll> vll;
const ll mod = 998244353;
ll Add(ll x, ll y) { return (x+y>=mod) ? (x+y-mod) : (x+y); }
ll Mul(ll x, ll y) { return x * y % mod; }
ll Mod(ll x) { return x < 0 ? (x + mod) : (x >= mod ? (x-mod) : x); }
ll cadd(ll &x, ll y) { return x = (x+y>=mod) ? (x+y-mod) : (x+y); }
ll cMul(ll &x, ll y) { return x = x * y % mod; }
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T> T cmax(T &x, T y) { return x = x > y ? x : y; }
template <typename T> T cmin(T &x, T y) { return x = x < y ? x : y; }
template <typename T>
T &read(T &r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
const int N = 1001000;
int n, m, deg[N];
vi eg[N];
ll ans;
ll Calc(int x) {
return (ll)eg[x].size() * (deg[x] - (ll)eg[x].size());
}
void Rev(int x) {
ans -= Calc(x);
for(auto v : eg[x]) {
ans -= Calc(v);
eg[v].pb(x);
ans += Calc(v);
}
eg[x].clear();
}
signed main() {
read(n); read(m);
for(int i = 1, u, v; i <= m; ++i) {
read(u); read(v);
if(u < v) std::swap(u, v);
eg[v].pb(u); ++deg[u]; ++deg[v];
}
for(int i = 1; i <= n; ++i) ans += Calc(i);
printf("%lld\n", ans);
int q; read(q);
for(int i = 1; i <= q; ++i) {
int u; read(u);
Rev(u);
printf("%lld\n", ans);
}
return 0;
}