#include using namespace std; #define rep(i, n) for (int i = 0; i < n; i++) #define rep2(i, x, n) for (int i = x; i <= n; i++) #define rep3(i, x, n) for (int i = x; i >= n; i--) #define each(e, v) for (auto &e : v) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() using ll = long long; using pii = pair; using pil = pair; using pli = pair; using pll = pair; const int MOD = 1000000007; // const int MOD = 998244353; const int inf = (1 << 30) - 1; const ll INF = (1LL << 60) - 1; template bool chmax(T &x, const T &y) { return (x < y) ? (x = y, true) : false; }; template bool chmin(T &x, const T &y) { return (x > y) ? (x = y, true) : false; }; struct io_setup { io_setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; template void print(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' '); } template void printn(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << '\n'; } template int lb(const vector &v, T x) { return lower_bound(begin(v), end(v), x) - begin(v); } template int ub(const vector &v, T x) { return upper_bound(begin(v), end(v), x) - begin(v); } template void unique(vector &v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } template vector iota(const vector &v, bool greater = false) { int n = v.size(); vector ret(n); iota(begin(ret), end(ret), 0); sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; }); return ret; } struct Union_Find_Tree { vector data; const int n; Union_Find_Tree(int n) : data(n, -1), n(n) {} int root(int x) { if (data[x] < 0) return x; return data[x] = root(data[x]); } int operator[](int i) { return root(i); } bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y], data[y] = x; return true; } int size(int x) { return -data[root(x)]; } bool same(int x, int y) { return root(x) == root(y); } void clear() { fill(begin(data), end(data), -1); } }; int main() { int N, M; cin >> N >> M; vector x(M), y(M); vector> idx(N), idy(N); rep(i, M) { cin >> x[i] >> y[i]; x[i]--, y[i]--; idx[x[i]].eb(y[i]); idy[y[i]].eb(x[i]); } Union_Find_Tree uf(N); rep(i, N) { int K = sz(idy[i]); rep(j, K - 1) { uf.unite(idy[i][j], idy[i][j + 1]); } } vector> s(N); vector cx(N, 0), cy(N, 0); rep(i, N) { int u = uf[i]; each(e, idx[i]) s[u].eb(e); cy[u]++; } rep(i, N) { unique(s[i]); cx[i] = sz(s[i]); } int K = N - accumulate(all(cx), 0); rep(i, K) cx.eb(1), cy.eb(0); vector dp(N + 1, -inf); dp[0] = 0; rep(i, N + 1) { rep3(j, N, 0) { if (dp[j] == -inf) continue; chmax(dp[j + cx[i]], dp[j] + cy[i]); } } int ans = inf; rep2(i, 0, N) { if (dp[i] != -inf) chmin(ans, N * (i + N - dp[i]) - i * (N - dp[i])); } cout << ans - M << '\n'; }