#pragma GCC optimize ("O2") #pragma GCC target ("avx2") #include using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (n); i++) #define rep1(i, n) for(int i = 1; i <= (n); i++) #define co(x) cout << (x) << "\n" #define cosp(x) cout << (x) << " " #define ce(x) cerr << (x) << "\n" #define cesp(x) cerr << (x) << " " #define pb push_back #define mp make_pair #define chmin(x, y) x = min(x, y) #define chmax(x, y) x = max(x, y) #define Would #define you #define please const int NV = 400001; map> E, E2; vector ba, E3[NV]; set vis; map S; int kazu[NV], memo[NV]; int NS; void dfs1(int A) { if (vis.find(A) == vis.end()) { vis.insert(A); for (int i : E[A]) dfs1(i); ba.pb(A); } } void dfs2(int A) { if (!S[A]) { S[A] = NS; chmax(kazu[NS], A); for (int i : E2[A]) dfs2(i); } } int dfs3(int A) { if (memo[A]) return memo[A]; int ret = kazu[A]; for (int i : E3[A]) chmax(ret, dfs3(i)); return memo[A] = ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; set list; rep(i, M) { int u, v; cin >> u >> v; E[u].pb(v); E2[v].pb(u); list.insert(u); list.insert(v); } for (auto p : E) { dfs1(p.first); } for (int i = N - 1; i >= 0; i--) if (S[ba[i]] == 0) { NS++; dfs2(ba[i]); } for (auto p : E) { for (int j : p.second) { if (S[p.first] != S[j]) E3[S[p.first]].pb(S[j]); } } ll kotae = 0; for (auto i : list) { kotae -= i; int j = S[i]; kotae += dfs3(j); } kotae += ll(N) * (N + 1) / 2; co(kotae); Would you please return 0; }