#include #include #include #include using namespace std; int main() { int n, m; cin >> n >> m; vector > adj(2*n); for (int i = 0; i < m; i++) { int r, c; cin >> r >> c; r--; c--; c += n; adj[r].push_back(c); adj[c].push_back(r); } vector > AB; struct DFS { int n; vector visited; vector > &adj; DFS(int n, vector > &adj) : n(n), visited(2*n, false), adj(adj) {} void dfs(int i, int &a, int &b) { visited[i] = true; if (i < n) a++; else b++; for (int j : adj[i]) if (!visited[j]) dfs(j, a, b); } pair dfs(int i) { int a = 0, b = 0; dfs(i, a, b); return {a, b}; } } dfs(n, adj); for (int i = 0; i < 2*n; i++) { if (!dfs.visited[i]) { auto [a, b] = dfs.dfs(i); AB.emplace_back(a, b); } } constexpr int INF = 1 << 30; vector bmin(n+1, INF), bmax(n+1, -INF); bmin[0] = bmax[0] = 0; for (auto [a, b] : AB) { for (int i = n - a; i >= 0; i--) { if (bmin[i] == INF) { assert(bmax[i] == -INF); continue; } bmin[i + a] = min(bmin[i + a], bmin[i] + b); bmax[i + a] = max(bmax[i + a], bmax[i] + b); } } int ans = n * n; for (int a = 0; a <= n; a++) { if (bmin[a] != INF) { const int b = 2 * a <= n ? bmax[a] : bmin[a]; ans = min(ans, (n - b) * (n - a) + a * b); } } cout << ans - m << '\n'; }