#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define SPEED ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FOR(i, a, b) for (ll i = a; i < b; ++i)
#define RFOR(i, b, a) for (ll i = b; i >= a; --i)
#define ALL(x) x.begin(), x.end()
#define DEBUG(args...) { string _s = #args; replace(ALL(_s), ' ', '\0');\
replace(ALL(_s), ',', ' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); _debug(_it, args);}
#define endl "\n"
#define F first
#define S second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void _debug(istream_iterator<string>) {}
template<typename T, typename... Args>
void _debug(istream_iterator<string> it, T first, Args... args) {
    cerr << ">> " << *it << " : " << first << endl; _debug(++it, args...);
}
template <typename T1, typename T2>
inline ostream& operator << (ostream& out, const pair<T1, T2>& p) {
    return out << "(" << p.F << ", " << p.S << ")";
}
template<typename T>
inline ostream& operator << (ostream& out, const vector<T>& v) {
    if (v.empty()) return out << "[]";
    else { out << '['; for (auto& e : v) { out << e << ", "; } return out << "\b\b]"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const set<T>& s) {
    if (s.empty()) return out << "{}";
    else { out << '{'; for (auto& e : s) { out << e << ", "; } return out << "\b\b}"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const unordered_set<T>& s) {
    return out << set<T>(ALL(s));
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const map<T1, T2>& m) {
    if (m.empty()) return out << "{}";
    out << '{'; for (auto& p : m) { out << p << ", "; } return out << "\b\b}";
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const unordered_map<T1, T2>& m) {
    return out << map<T1, T2>(ALL(m));
}
template<typename T>
inline ostream& operator << (ostream& out, const ordered_set<T>& s) {
    return out << set<T>(ALL(s));
}

typedef long long ll;
typedef long double ld;
typedef vector<long long> vll;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;
typedef unordered_map<ll, ll> STll;
/************************************** MAIN PROGRAM ********************************************/
const int MAX = 701;
vector<int> adj[MAX];
bool marked[MAX];
bool colorOf[MAX];
const bool RED = true;
const bool BLUE = false;

ll countRED = 0, countBLUE = 0;

void dfs(int v) {
   //DEBUG(v, colorOf[v])
    countRED += colorOf[v] == RED;
    countBLUE += colorOf[v] == BLUE;
    marked[v] = true;
    for (int w : adj[v]) {
        if (!marked[w]) {
            colorOf[w] = !colorOf[v];
            dfs(w);
        } else if (colorOf[v] == colorOf[w]) {
            cout << "-1";
            exit(0);
        }
    }
}

int main()
{
  //  freopen("input.txt", "r", stdin);
    SPEED
    ll n, m;
    cin >> n >> m;
    set<pair<int, int>> edges;
    FOR(_, 0, m)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edges.insert({u, v});
        edges.insert({v, u});
    }
    FOR(i, 0, n)
    {
        FOR(j, 0, n)
        {
            if (i == j) continue;
            if (edges.count({i, j})) continue;
            adj[i].push_back(j);
        }
    }
    vector<pair<int, int>> components; /// {red, blue}
    FOR(i, 0, n)
    {
        if (marked[i]) continue;
        countRED = 0, countBLUE = 0;
        dfs(i);
        components.push_back({countRED, countBLUE});
    }
    int len = components.size();
    vector<vector<int>> dp(len + 1, vector<int>(2 * n, -1));     /// max in first city if j are in second considering pref len = i
    dp[0][0] = 0;
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < n; ++j) {
            int blue = components[i].second;
            int red = components[i].first;
            /// take blue for first city and red for second
            if (dp[i][j] == -1) continue;
            dp[i + 1][j + red] = max(dp[i + 1][j + red], blue + dp[i][j]);
            dp[i + 1][j + blue] = max(dp[i + 1][j + blue], red + dp[i][j]);
        }
    }

    ll ans = LLONG_MAX;
    for (int i = 0; i <= n; ++i) {
        if (dp[len][i] != -1) {
            int j = dp[len][i];
            ans = min(ans, (ll)i * (i - 1) / 2 + j * (j - 1) / 2);
        }
    }
    cout << ans;
}
/************************************** END OF PROGRAM ******************************************/
/** Stuff you should look for:
 * int overflow, array bounds, over-counting, graph is not a tree/connected
 * special cases (n=1?), set/unordered_set TLE, multi-set/set error
 * do something instead of nothing and stay organized
 */


Measured memory_bytes: 27008