import core.stdc.stdio;
import std.typecons;
import std.stdio;
import std.algorithm;
import std.math;

void main(){
	int v,e;
	scanf("%d%d",&v,&e);
	int[][] graph = new int[][v];
	foreach(i;0..e){
		int a,b;
		scanf("%d%d",&a,&b);
		graph[--a]~=--b;
		graph[b]~=a;
	}
	int[] d=new int[v];
	int[] s=new int[v];
	int[] t=new int[v];
	void dfs(int i,int b,ref int e,ref int f){
		if(d[i])
			return;
		d[i]=b;
		e++;
		foreach(c;graph[i])
			dfs(c,3-b,f,e);
	}
	foreach(i;0..v)
		dfs(i,1,s[i],t[i]);
	foreach(i;0..v)
		foreach(c;graph[i])
			if(d[i]==d[c]){
				printf("-1\n");
				return;
			}
	int g;
	int[int] h;
	foreach(i;0..v)
		if(s[i]||t[i]){
			g+=min(s[i],t[i]);
			int w=abs(s[i]-t[i]);
			if(w in h)
				h[w]++;
			else
				h[w]=1;
		}
	int[] dp=new int[v+1];
	static immutable int inf=1145141919;
	dp[]=inf;
	dp[0]=0;
	foreach(q;h.byKeyValue){
		foreach(ref x;dp)
			if(x<inf)x=0;
		foreach(i;q.key..v+1)
			if(dp[i-q.key]<q.value)
				dp[i]=min(dp[i],dp[i-q.key]+1);
	}
//	writeln(g," ",dp);
	long ans=0;
	foreach(i,x;dp)
		if(x<inf)
			ans=max(ans,cast(long)(g+i)*(v-g-i));
	printf("%lld\n",ans-e);
}