#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ in >> p.first >> p.second; return in; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

int cnt;
set<pair<int, int>> anss;
struct Graph{
    struct Node{
        vector<int> dests;
        int color = 0;
        bool rev = false;
    };
    vector<Node> nodes;
    Graph(int num): nodes(num){ }
    int id(Node* n){ return n - &nodes[0]; }
    int id(Node& n){ return &n - &nodes[0]; }
    void print(){ for(auto& node : nodes){ prints(id(node), node.dests); } }
    void addEdge(int from, int dest){
        nodes[from].dests.push_back(dest);
    }
    void addEdge2(int from, int dest){
        addEdge(from, dest);
        addEdge(dest, from);
    }
    pair<int, int> dfs(int idx, int prev = 2){
        nodes[idx].color = prev == 1 ? 2 : 1;
        pair<int, int> ret(prev == 2, prev == 1);
        for(int didx : nodes[idx].dests){
            if(nodes[didx].color){
                if(nodes[didx].color == nodes[idx].color){
                    cout << -1 << '\n';
                    exit(0);
                }
                // cnt++;
                // prints(idx, didx);
                // anss.erase(pair<int, int>(min(idx, didx), max(idx, didx)));
                continue;
            }
            auto p = dfs(didx, nodes[idx].color);
            ret.first += p.first;
            ret.second += p.second;
        }
        // printd(idx, ret);
        return ret;
    }
    void rev(int idx, int prev, int p = -1){
        if(nodes[idx].rev){ return; }
        nodes[idx].rev = true;
        nodes[idx].color = nodes[idx].color == 1 ? 2 : 1;
        for(int didx : nodes[idx].dests){
            rev(didx, nodes[idx].color, didx);
        }
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    Graph g(n);
    set<pair<int, int>> es;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            es.emplace(i, j);
        }
    }
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        anss.emplace(min(a, b), max(a, b));
        es.erase(pair<int, int>(min(a, b), max(a, b)));
    }
    prints(es);
    for(auto& e : es){
        g.addEdge2(e.first, e.second);
    }
    int ans = m;
    int a = 0, b = 0;
    vector<int> ds;
    for(int i = 0; i < n; i++){
        if(g.nodes[i].color){ continue; }
        auto p = g.dfs(i);
        ds.push_back(abs(p.first - p.second));
        // auto p = g.dfs(i, a < b);
        // auto p = g.dfs(i, a < b ? 2 : 1);
        if((a < b && p.first < p.second) ||
           (a > b && p.first > p.second)){
            g.rev(i, g.nodes[i].color);
            a += p.second; b += p.first;
        }else{
            a += p.first; b += p.second;
        }
        // a += p.first; b += p.second;
        // if(a < b){
        //     a += max(p.first, p.second);
        //     b += min(p.first, p.second);
        // }else{
        //     a += min(p.first, p.second);
        //     b += max(p.first, p.second);
        // }
        printd(a, b);
    }
    printd(anss);
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(g.nodes[i].color && g.nodes[i].color != g.nodes[j].color){
                anss.erase(pair<int, int>(i, j));
            }
        }
    }
    // cout << anss.size() << '\n';
    // cout << n * (n - 1) / 2 - a * b << '\n';
    vector<int> dp(2000);
    dp[1000] = 1;
    for(auto& d : ds){
        vector<int> next(2000);
        for(int i = 0; i < 2000; i++){
            if(dp[i]){
                // next[i] = 1;
                if(i - d >= 0){ next[i - d] = 1; }
                if(i + d < 2000){ next[i + d] = 1; }
            }
        }
        dp = next;
    }
    int mini = M;
    for(int i = 0; i < 2000; i++){
        if(dp[i]){
            mini = min(mini, abs(i - 1000));
        }
    }
    printd(n * (n - 1) / 2 - a * b);
    printd(a, b, mini, (a + b + mini) / 2, (a + b - mini + 1) / 2);
    cout << n * (n - 1) / 2 - ((a + b + mini) / 2) * ((a + b - mini + 1) / 2) << '\n';
    // cout << m - cnt / 2 << '\n';
    // cout << m - n / 2 << '\n';
    // cout << ans << '\n';
}


Measured memory_bytes: 14592