#include #include #include #include using namespace std; int main() { int N, M; cin >> N >> M; vector B(M), C(M); for (int i = 0; i < M; ++i) { cin >> B[i] >> C[i]; --B[i], --C[i]; } vector comp; for (int i = 0; i < M; ++i) { comp.push_back(B[i]); comp.push_back(C[i]); } sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); vector > G(comp.size()); for (int i = 0; i < M; ++i) { int bp = lower_bound(comp.begin(), comp.end(), B[i]) - comp.begin(); int cp = lower_bound(comp.begin(), comp.end(), C[i]) - comp.begin(); G[bp].push_back(cp); } vector vis(comp.size(), false); vector dp(comp.size()); function dfs = [&](int pos) { vis[pos] = true; int res = pos; for (int i : G[pos]) { if (vis[i]) { res = max(res, dp[i]); } else { res = max(res, dfs(i)); } } dp[pos] = res; return res; }; for (int i = 0; i < comp.size(); ++i) { if (!vis[i]) dfs(i); } long long ans = 1LL * N * (N + 1) / 2; for (int i = 0; i < comp.size(); ++i) { ans += comp[dp[i]] - comp[i]; } cout << ans << endl; return 0; }