/*Bismillahir Rahmanir Rahim*///{
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1;
const double eps = 1e-6, ldeps = 1e-9;
struct Dbg {
static constexpr auto &os = cout;   // replace by cerr in interactive.
template<class C> static auto dud(C *x)->decltype(os << *x, 0);
template<class C> static char dud(...);
template<class C> typename enable_if<sizeof dud<C>(0)!=1, Dbg&>::type operator<<(const C &x) { os << x; return *this; }
template<class C> Dbg &dump(C b, C e) {
    *this << "\n[";
    int cur = 0;
    for (C i = b; i!=e and cur<26; i++, cur++) *this << ", "+2*(i==b) << *i;
    return *this << ']';
}
template<class C> typename enable_if<sizeof dud<C>(0)==1, Dbg&>::type operator<<(const C &x) {
    return dump(begin(x), end(x));
}
template<class C, size_t X> typename enable_if<!is_same<C, const char>::value, Dbg&>::type operator <<(C (&x)[X]) {
    return dump(begin(x), end(x));
}
template<class B, class C> Dbg &operator <<(const pair<B, C> &x) {
    return *this << '{' << x.first << ", " << x.second << '}';
}
template<class C, size_t Y> struct TP {
    void operator()(Dbg& os, const C &t) { TP<C, Y-1>()(os, t); os << ", " << get<Y-1>(t); }
};
template<class C> struct TP<C, 1> { void operator()(Dbg& os, const C &t) { os << get<0>(t); } };
template<class... C> Dbg& operator<<(const tuple<C...> &t) {
    os << '{', TP<decltype(t), sizeof...(C)>()(*this, t); return *this << '}';
}
Dbg &operator<<(ostream&(*x)(std::ostream&)) { os << x; return *this; }
} dbg;
void err(istringstream *iss) { delete iss; }
template<class C, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args ...);
}
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(string(#args)), args), dbg << endl
#define ASSERT(a, o, b) { if (!((a) o (b))) bug(a, b), assert((a) o (b)); }
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
int T, Q, cn;//}
const int inf = 1000000007, mxn = 705;

int n, m, col[mxn];
bool adj[mxn][mxn];

int cntZero, cntOne, dp[mxn][mxn<<1|1];

void dfs(int u) {
    if (col[u]) cntOne++;
    else cntZero++;
    for (int i = 1; i <= n; i++) if (i!=u and !adj[u][i]) {
        if (col[i]==-1) col[i] = col[u]^1, dfs(i);
        else if (col[i]==col[u]) cout << -1 << '\n', exit(0);
    }
}

signed main() { ios::sync_with_stdio(0); cin.tie(NULL); cout.precision(11);

/*It's clear that we need to minimize absolute difference of sizes of both cities.
Create the complement graph, every connected component must be bicolorable and we can swap the colors to balance, which
can easily be done by dp.*/

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = adj[v][u] = 1;
    }

    memset(col, -1, sizeof(col));
    vector<int> v;
    for (int i = 1; i <= n; i++) {
        if (col[i]==-1) col[i] = 0, cntZero = cntOne = 0, dfs(i), v.push_back(abs(cntOne-cntZero));
    }

    int sz = sz(v);
    for (int i = -n; i <= n; i++) {
        dp[sz][i+n] = abs(i);
    }
    for (int i = sz-1; i >= 0; i--) {
        for (int j = -n; j <= n; j++) {
            dp[i][j+n] = inf;
            if (j+v[i]<=n) dp[i][j+n] = min(dp[i][j+n], dp[i+1][j+v[i]+n]);
            if (j-v[i]>=-n) dp[i][j+n] = min(dp[i][j+n], dp[i+1][j-v[i]+n]);
        }
    }
    // a+b == n, a-b == dp[0][n]. ==> a = (n+dp[0][n])/2, b = (n-dp[0][n])/2
    int taka = (n+dp[0][n])/2, hashi = (n-dp[0][n])/2;
    cout << taka*(taka-1)/2+hashi*(hashi-1)/2 << '\n';
}

Measured memory_bytes: 4608