#include "bits/stdc++.h" using namespace std; #define int long long #define REP(i, n) for (int i = 0; i < (int)n; ++i) #define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i) #define FOR(i, s, n) for (int i = s; i < (int)n; ++i) #define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i) #define ALL(a) a.begin(), a.end() #define IN(a, x, b) (a <= x && x < b) templateistream&operator >>(istream&is,vector&vec){for(T&x:vec)is>>x;return is;} templateinline void out(T t){cout << t << "\n";} templateinline void out(T t,Ts... ts){cout << t << " ";out(ts...);} templateinline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;} templateinline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;} constexpr int INF = 1e18; template< typename T > struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template< typename T > using Edges = vector< edge< T > >; template< typename T > using WeightedGraph = vector< Edges< T > >; using UnWeightedGraph = vector< vector< int > >; template< typename T > using Matrix = vector< vector< T > >; template< typename G > struct StronglyConnectedComponents { const G &g; UnWeightedGraph gg, rg; vector< int > comp, order, used; StronglyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) { for(int i = 0; i < g.size(); i++) { for(auto e : g[i]) { gg[i].emplace_back((int) e); rg[(int) e].emplace_back(i); } } } int operator[](int k) { return comp[k]; } void dfs(int idx) { if(used[idx]) return; used[idx] = true; for(int to : gg[idx]) dfs(to); order.push_back(idx); } void rdfs(int idx, int cnt) { if(comp[idx] != -1) return; comp[idx] = cnt; for(int to : rg[idx]) rdfs(to, cnt); } void build(UnWeightedGraph &t) { for(int i = 0; i < gg.size(); i++) dfs(i); reverse(begin(order), end(order)); int ptr = 0; for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++; t.resize(ptr); for(int i = 0; i < g.size(); i++) { for(auto &to : g[i]) { int x = comp[i], y = comp[to]; if(x == y) continue; t[x].push_back(y); } } } }; template< typename T > struct Compress { vector< T > xs; Compress() = default; Compress(const vector< T > &vs) { add(vs); } Compress(const initializer_list< vector< T > > &vs) { for(auto &p : vs) add(p); } void add(const vector< T > &vs) { copy(begin(vs), end(vs), back_inserter(xs)); } void add(const T &x) { xs.emplace_back(x); } void build() { sort(begin(xs), end(xs)); xs.erase(unique(begin(xs), end(xs)), end(xs)); } vector< int > get(const vector< T > &vs) const { vector< int > ret; transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) { return lower_bound(begin(xs), end(xs), x) - begin(xs); }); return ret; } int get(const T &x) const { return lower_bound(begin(xs), end(xs), x) - begin(xs); } const T &operator[](int k) const { return xs[k]; } }; signed main(){ int N, M; cin >> N >> M; int n = N; vectora(M), b(M); REP(i, M) { cin >> a[i] >> b[i]; } Compress c; c.add(a); c.add(b); c.build(); a = c.get(a); b = c.get(b); N = c.xs.size(); vector>g(N); REP(i, M) { g[a[i]].emplace_back(b[i]); } StronglyConnectedComponents scc(g); vector>buff; scc.build(buff); vectorma(N); vectorcnt(N); REP(i, N) { CHMAX(ma[scc[i]], c[i]); ++cnt[scc[i]]; } vectordp(N); REP(i, N) dp[i] = ma[scc[i]]; vectorvisit(N); { auto dfs = [&](auto&&f, int now) -> int { visit[now] = 1; for(auto e: g[now]) { if(visit[e]) { CHMAX(dp[now], dp[e]); } else { CHMAX(dp[now], f(f, e)); } } return dp[now]; }; REP(i, N) { if(visit[i] == 0) dfs(dfs, i); } } //REP(i, N) out(i, dp[i], scc[i]); int ans = n * (n + 1) / 2; REP(i, N) ans -= c.xs[i]; REP(i, N) { ans += dp[i]; } out(ans); }