#include using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,s,e) for(int i=(s); i<(int)(e); i++) #define repr(i, n) REPR(i, n, 0) #define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--) #define all(r) r.begin(),r.end() #define rall(r) r.rbegin(),r.rend() typedef long long ll; typedef vector vi; typedef vector vl; const ll INF = 1e18; const ll MOD = 1e9 + 7; template T chmax(T& a, const T& b){return a = (a > b ? a : b);} template T chmin(T& a, const T& b){return a = (a < b ? a : b);} //有向、無向グラフ共通クラス(隣接リスト) struct Graph { int n; using WEIGHT_TYPE = long long; const WEIGHT_TYPE INF = 1e18; struct Edge { int to; WEIGHT_TYPE weight; }; struct Edge2 { int from; int to; WEIGHT_TYPE weight; }; vector> es; Graph(int n) : n(n), es(n) {} // dijkstra O(E log V) vector dijkstra(int s) { vector d(n, INF); d[s] = 0; using P = pair; priority_queue, greater

> q; q.push({0LL, s}); while(!q.empty()) { auto p = q.top(); q.pop(); int cur = p.second; auto cost = p.first; if(d[cur] < p.first) continue; for(auto &e : es[cur]) { int to = e.to; auto dist = e.weight + cost; if(dist < d[to]) { d[to] = dist; q.push({dist, to}); } } } return d; } // dijkstra O(V^2) vector dijkstra2(int s) { vector d(n, INF); d[s] = 0; vector used(n); auto mat = getEdgeMat(); while(1) { int cur = -1; rep(i, n) { if(used[i]) continue; if(cur == -1 || d[i] < d[cur]) cur = i; } if(cur == -1) break; used[cur] = 1; rep(i, n) { chmin(d[i], d[cur] + mat[cur][i]); } } return d; } // warshall_floyd O(n^3) vector> warshall_floyd() { // vector> d(n, vector(n, INF)); // rep(i, n) d[i][i] = 0LL; // rep(i, n) for (auto && e : es[i]) { // int j = e.to; // chmin(d[i][j], e.weight); // } auto d = getEdgeMat(); rep(k, n) rep(i, n) rep(j, n) { chmin(d[i][j], d[i][k] + d[k][j]); } return d; } // 頂点sから到達できるか vector getVisitable(int s) { vector ret(n); queue q; q.push(s); ret[s] = true; while(!q.empty()) { auto cur = q.front(); q.pop(); for(auto &&e : es[cur]) { if(!ret[e.to]) { ret[e.to] = true; q.push(e.to); } } } return ret; } // 2部グラフ判定 bool isBipartile() { vector memo(n, -1); rep(i, n) { if(memo[i] != -1) continue; queue q; q.push(i); memo[i] = 0; while(!q.empty()) { auto v = q.front(); q.pop(); for(auto &&e : es[v]) { auto u = e.to; if(memo[u] == -1) { memo[u] = !memo[v]; q.push(u); } else if(memo[u] == memo[v]) { return false; } } } } return true; } vector> getEdgeMat() { vector> mat(n, vector(n, INF)); rep(i, n) mat[i][i] = 0; rep(i, n) { for(auto &&e : es[i]) chmin(mat[i][e.to], e.weight); } return mat; } }; // 無向グラフ struct GraphUD : public Graph { GraphUD(int n) : Graph(n) {} void add_edge(int from, int to, WEIGHT_TYPE weight) { es[from].push_back({to, weight}); es[to].push_back({from, weight}); } vector getEdge2() { vector ret; rep(i, n) for(auto &&e : es[i]) { if(i < e.to) ret.push_back({i, e.to, e.weight}); } return ret; } // 橋の検出 // http://nupioca.hatenadiary.jp/entry/2013/11/03/200006 // Calculate bridges in a undirected graph. // Assume graph is connected and has no parallel edges or self-loops. vector getBridges() { int V = n; // res: bridges vector res; // assume at least the first vertex exists vector low(V, -1); // lowest reacheable index vector pre(V, -1); // pre-order index int count = 0; // pre-order index counter // v: current node // from: parent node function dfs = [&](int v, int from) { pre[v] = count++; low[v] = pre[v]; for(auto &&e : es[v]) { int to = e.to; if(pre[to] == -1) { // destination has not been visited // visit destination and update low[v] low[v] = min(low[v], dfs(to, v)); if(low[to] == pre[to]) { // edge is not contained in a closed path -> bridge res.push_back({v, to, e.weight}); } } else { if(from == to) { // ignore a path to parent continue; } low[v] = min(low[v], low[to]); } } return low[v]; }; dfs(0, -1); // start dfs from vertex 0 return res; } }; // 有向グラフ struct GraphD : public Graph { GraphD(int n) : Graph(n) {} void add_edge(int from, int to, WEIGHT_TYPE weight) { es[from].push_back({to, weight}); } vector getEdge2() { vector ret; rep(i, n) for(auto &&e : es[i]) { ret.push_back({i, e.to, e.weight}); } return ret; } GraphD getReverseGraph() { GraphD g(n); rep(i, n) for(auto &&e : es[i]) { g.add_edge(e.to, i, e.weight); } return g; } vector> scc() { vector> res; vector cmp(n); vector vs; vector> r_es(n); rep(i, n) for(auto &&e : es[i]) { int j = e.to; r_es[j].push_back(i); } vector used(n); function dfs = [&](int v) { used[v] = true; for(auto &&e : es[v]) { int to = e.to; if(!used[to]) dfs(to); } vs.push_back(v); }; function rdfs = [&](int v, int k) { used[v] = true; cmp[v] = k; for(auto &&to : r_es[v]) { if(!used[to]) rdfs(to, k); } }; fill(all(used), 0); vs.clear(); for(int v = 0; v < n; v++) { if(!used[v]) dfs(v); } fill(all(used), 0); int k = 0; for(int i = vs.size() - 1; i >= 0; i--) { if(!used[vs[i]]) rdfs(vs[i], k++); } res.clear(); res.resize(k); for(int i = 0; i < n; i++) { res[cmp[i]].push_back(i); } return res; } // bellmanFord 負閉路があるなら, dist[s] = INF | O(VE) vector bellmanFord(int s) { vector dist(n, INF); dist[s] = 0; auto es = getEdge2(); rep(i, n) { for(auto &&e : es) { if(dist[e.to] > dist[e.from] + e.weight) { dist[e.to] = dist[e.from] + e.weight; if(i == n - 1) { dist[s] = INF; return dist; } } } } return dist; } // bellmanFord s->tの経路上に負閉路があるなら, dist[s] = INF | O(VE) vector bellmanFord2(int s, int t) { vector dist(n, INF); auto f1 = getVisitable(s); auto f2 = getReverseGraph().getVisitable(t); dist[s] = 0; auto es = getEdge2(); rep(i, n) { for(auto &&e : es) { if(!(f1[e.from] && f2[e.to])) continue; if(dist[e.to] > dist[e.from] + e.weight) { dist[e.to] = dist[e.from] + e.weight; if(i == n - 1) { dist[s] = INF; return dist; } } } } return dist; } }; #define DEBUG_MODE #ifdef DEBUG_MODE #define dump(x) cout << #x << " : " << x << " " #define dumpL(x) cout << #x << " : " << x << '\n' #define LINE cout << "line : " << __LINE__ << " " #define LINEL cout << "line : " << __LINE__ << '\n' #define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << " " #define dumpVL(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl #define STOP assert(false) #else #define dump(x) #define dumpL(x) #define LINE #define LINEL #define dumpV(v) #define dumpVL(v) #define STOP assert(false) #endif #define mp make_pair namespace std { template ostream &operator <<(ostream& out, const pair& a) { out << '(' << a.fi << ", " << a.se << ')'; return out; } } int main(){ ll n, m; cin >> n >> m; vl x(m), y(m); rep(i, m) { cin >> x[i] >> y[i]; --x[i]; --y[i]; } ll ans = n*(n+1)/2; // dumpL(ans); map mp; rep(i, m) { mp[x[i]] = 0; mp[y[i]] = 0; } for(auto&& p: mp) ans -= p.first+1; vl r_mp; { int cnt= 0; for(auto& p : mp) { p.second = cnt++; r_mp.emplace_back(p.first); } } n = mp.size(); GraphD g(n); rep(i, m) g.add_edge(mp[x[i]], mp[y[i]], 1); auto scc = g.scc(); vl d(n); rep(i, n) d[i] = r_mp[i]+1; repr(i, scc.size()) { ll ma = 0; for(auto&& x: scc[i]) for(auto&& y: g.es[x]) chmax(ma, d[y.to]); for(auto&& x: scc[i]) chmax(d[x], ma); } cout << ans + accumulate(all(d), 0LL) << '\n'; // dumpL(ans); return 0; }