#include<bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")

#define isz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define isz(x) int(x.size())
#define ull unsigned long long
#define vb vector<bool>
#define vvb vector<vb>
#define vvvb vector<vvb>
#define vi vector<int>
#define vll vector<ll>
#define vch vector<char>
#define vvch vector<vch>
#define vvvch vector<vvch>
#define vvi vector<vector<int>>
#define vvvi vector<vvi>
#define vvll vector<vector<ll>>
#define vvvll vector<vvll>
#define vpii vector<pair<int,int>>
#define vvpii vector<vpii>
#define forn(i,n) for(int i=0;i<(int)n;++i)
#define pb push_back

using namespace std;

const int UNDEF = -1;
const int MOD = 1e9 + 7;
const int INF = 1e9;

int main() {
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);

    int N,M;
    cin>>N>>M; // кол-во вершин , кол-во рёбер

    vvi g(1+N);
    for(int i=1;i<=M;++i){ // считываю рёбра
        int a,b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }

    vi color(1+N,UNDEF); // каждая вершина изначально цвета не имеет UNDEF = -1

    function<void(int,int,int&,int&)> dfs=[&](int u,int col,int& cnt0,int& cnt1){
        color[u]=col;

        if(col==0) cnt0++;
        else cnt1++;

        for(int to : g[u]){
            assert(color[to]==UNDEF || color[to]==1-col);
            if(color[to]==UNDEF) dfs(to,1-col,cnt0,cnt1);
        }
    };

    vpii a;// a[i] - хранит разбиение i-ой компоненты связности на доли (a[i].fi - кол-во долей цвета 0, a[i].se - кол-во долей цвета 1)
    for(int i=1;i<=N;++i){
        if(color[i]==UNDEF){  // Запускаюсь из каждой компоненты связности
            int cnt0=0,cnt1=0; // кол-во вершин цвета 0(1 доля),кол-во вершин цвета 1 (2 доля)
            dfs(i,1,cnt0,cnt1);
            a.pb({cnt0,cnt1});
        }
    }

   vb dp(1+N,false); // рюкзак dp[i] значит,что можно набрать i вершин в 1 долю конечного двудольного графа
   dp[0]=true;

   for(int i=0;i<isz(a);++i){
       for(int j=N;j>=0;--j){
           if(a[i].fi<=j) dp[j] = (dp[j] || dp[j-a[i].fi]);
           if(a[i].se<=j) dp[j] = (dp[j] || dp[j-a[i].se]);
       }
   }

   int best=-1;
   for(int i=1;i<=N;++i){ // перебираю варианты конечного двудольного графа,если i-вершин в первой доле ,то N-i во второй
      if(dp[i]) best=max(best,i * (N-i));
   }

   cout<<best-M; // ответ

   return 0;
}