#define _USE_MATH_DEFINES #include using namespace std; map zip; vector unzip; template void compress(vector& v) { for (int i = 0; i < (int) v.size(); i++) unzip.push_back(v[i]); sort(unzip.begin(), unzip.end()); unzip.erase(unique(unzip.begin(), unzip.end()), unzip.end()); for (int i = 0; i < (int) unzip.size(); i++) zip[unzip[i]] = i; } class StronglyConnectedComponents { private: int siz; int itr = 0; vector done; vector order, comp; void dfs (int cur, const vector>& g) { done[cur] = true; for (int nxt : g[cur]) { if (!done[nxt]) dfs(nxt, g); } order.push_back(cur); } void rdfs (int cur, const vector>& rg) { done[cur] = true; comp[cur] = itr; for (int nxt : rg[cur]) { if (!done[nxt]) rdfs(nxt, rg); } } void build (const vector>& g, const vector>& rg) { for (int i = 0; i < siz; ++i) if (!done[i]) dfs (i, g); reverse(order.begin(), order.end()); fill(done.begin(), done.end(), false); for (int i = 0; i < siz; ++i) if (!done[order[i]]) rdfs (order[i], rg), ++itr; } public: StronglyConnectedComponents(const vector>& g, const vector>& rg, const int& n) : siz(n), done(siz, false), comp(siz, -1) { build(g, rg); } bool has_cycle() { return *max_element(comp.begin(), comp.end()) < siz - 1; } vector get_comp() { return comp;} }; using SCC = StronglyConnectedComponents; int dfs (int cur, vector>& g, vector& val, vector& vis) { if (vis[cur]) return val[cur]; vis[cur] = 1; for (int nxt : g[cur]) { val[cur] = max(val[cur], dfs(nxt, g, val, vis)); } return val[cur]; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector all; vector b(m), c(m); for (int i = 0; i < m; i++) { cin >> b[i] >> c[i]; all.push_back(b[i]); all.push_back(c[i]); } compress(all); for (int i = 0; i < m; i++) { b[i] = zip[b[i]]; c[i] = zip[c[i]]; } int nn = zip.size(); vector> g(nn), rg(nn); for (int i = 0; i < m; i++) { g[b[i]].push_back(c[i]); rg[c[i]].push_back(b[i]); } SCC scc(g, rg, nn); vector comp = scc.get_comp(); int nnn = *max_element(comp.begin(), comp.end()) + 1; vector> gg(nnn); vector val(nnn); for (int i = 0; i < m; i++) { assert(comp[b[i]] < nnn); assert(comp[c[i]] < nnn); val[comp[b[i]]] = max(val[comp[b[i]]], unzip[b[i]]); val[comp[c[i]]] = max(val[comp[c[i]]], unzip[c[i]]); if (comp[b[i]] == comp[c[i]]) continue; gg[comp[b[i]]].insert(comp[c[i]]); } vector vis(nnn); for (int i = 0; i < nnn; i++) dfs (i, gg, val, vis); long long ans = 1LL * n * (n + 1) / 2; set app; for (auto x : b) { if (app.count(x)) continue; app.insert(x); int y = unzip[x]; ans -= y; assert(y <= val[comp[x]]); ans += val[comp[x]]; } cout << ans << endl; return 0; }