Problem: Example

Input

8 5
1 2
6 5
6 4
1 3
4 7


Output

11

Solution (in CPP):

Solution:
//
//  2370.cpp
//
//
//  Created by Yoshida Satoshi on 2018/11/07.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>

#define MAX 100010

using namespace std;

typedef long long ll;

struct D
{
    int a,b;
    ll d;
    
    bool operator<(const D& rhs)const
    {
        return d>rhs.d;
    }
};

struct UF
{
    vector<int> p;
    
    
    UF(int n):p(n)
    {
        for(int i=0;i<n;i++) p[i]=i;
    }
    
    int root(int x)
    {
        if(p[x]==x) return x;
        else        return p[x]=root(p[x]);
    }
    
    void unite(int x,int y)
    {
        int rx=root(x);
        int ry=root(y);
        p[rx]=ry;
    }
    
    bool same(int x,int y)
    
    {
        int rx=root(x);
        int ry=root(y);
        return rx==ry;
    }
};

struct Graph
{
    int v,e;
    vector<int> p[MAX];//iとconnectedなvertex
    ll even[MAX]={};
    ll odd[MAX]={};
    int c[MAX]={};
    ll ans=0;
    
    
    void input()
    {
        cin>>v>>e;
        int a,b;
        for(int i=0;i<e;i++)
        {
            cin>>a>>b;
            a--;b--;
            p[a].push_back(b);
            p[b].push_back(a);
        }
    }
    
    void dfs(int x,int col,int l)
    {
        if(c[x]==-1*col)
        {
            ans=-1;return;
        }
        if(ans==-1) return;
        if(c[x]!=0) return;
        
        c[x]=col;
        if(col==1) odd[l]++;
        else   even[l]++;
        
        for(int i=0;i<p[x].size();i++)
        {
            int y=p[x][i];
            dfs(y,-1*col,l);
        }
    }
    
    void solve()
    {
        int l=0;
        for(int i=0;i<v;i++)
        {
            if(c[i]==0)
            {
                dfs(i,1,l);
                l++;
            }
        }
        
        if(ans!=-1)
        {
            int d[MAX];
            int m[MAX]={};
            ll sum=0;
            for(int i=0;i<l;i++)
            {
                if(even[i]<odd[i]) swap(even[i],odd[i]);
                d[i]=even[i]-odd[i];
                sum+=odd[i];
                //ans+=even[i]*odd[i];
            }
            //ans-=e;
            
            int dp[MAX];
            
            sort(d,d+l);
            
            int tmp=-1;
            int cnt=-1;
            
            for(int i=0;i<l;i++)
            {
                if(d[i]==tmp) m[cnt]++;
                else
                {
                    cnt++;
                    tmp=d[i];
                    d[cnt]=d[i];
                    m[cnt]++;
                }
            }
            for(int i=0;i<=v;i++)
            {
                dp[i]=-1;
            }
            dp[0]=0;
            
            for(int i=0;m[i]>0;i++)
            {
                for(int j=0;j<=v;j++)
                {
                    if(dp[j]>=0) dp[j]=m[i];
                    else if(j>=d[i]&&dp[j-d[i]]>0) dp[j]=dp[j-d[i]]-1;
                    else         dp[j]=-1;
                }
            }
            
            ll ans2=0;
            for(int i=0;i<=v;i++)
            {
                if(dp[i]>=0) ans2=max(ans2,(sum+i)*(v-sum-i));
            }
            
            ans2-=e;
            ans=ans2;
            
            
            /*
            UF uf(4*l);//0~l-1:even is -1,l~2l-1:even is 1,2l~:odd is -1,3l~:odd is 1
            vector<D> d;
            
            
            for(int i=0;i<l;i++)
            {
                for(int j=0;j<i;j++)
                {
                    d.push_back({i,j,(even[i]*even[j]+odd[i]*odd[j])-(even[i]*odd[j]+odd[i]*even[j])});
                }
            }
            sort(d.begin(),d.end());
            
            for(int i=0;i<d.size();i++)
            {
                int x=d[i].a;int y=d[i].b;
                if(!uf.same(d[i].a,d[i].b)&&!uf.same(d[i].a+l,d[i].b+l))
                {
                    uf.unite(d[i].a,d[i].b+l);
                    uf.unite(d[i].a+l,d[i].b);
                    uf.unite(d[i].a+2*l,d[i].b+3*l);
                    uf.unite(d[i].a+3*l,d[i].b+2*l);
                    ans+=(even[x]*even[y]+odd[x]*odd[y]);
                }
                else if(!uf.same(d[i].a+2*l,d[i].b)&&!uf.same(d[i].a+3*l,d[i].b+l))
                {
                    uf.unite(d[i].a+2*l,d[i].b+l);
                    uf.unite(d[i].a+3*l,d[i].b);
                    uf.unite(d[i].a,d[i].b+3*l);
                    uf.unite(d[i].a+l,d[i].b+2*l);
                    ans+=(even[x]*odd[y]+odd[x]*even[y]);
                }
            }
             */
        }
        cout<<ans<<endl;
    }
    
};

int main()
{
    Graph g;
    g.input();
    g.solve();
    
    return 0;
}