using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static List<int>[] li;
	static int[] b,c;
	static int n;
	static int[][] h;
	static bool bo=true;
	static void Main(){
		Sc sc=new Sc();
		var s=sc.Ia;
		n=s[0];
		int m=s[1];
		li=new List<int>[n+1];
		b=new int[n+1];
		h=new int[n+1][];
		for(int i=1;i<=n;i++){
			h[i]=new int[n+1];
		}
		for(int i=0;i<m;i++){
			var e=sc.Ia;
			h[e[0]][e[1]]=1;
			h[e[1]][e[0]]=1;
		}
		var li2=new List<int[]>();
		for(int i = 1;i<=n;i++) {
			c=new int[4];
			if(b[i]==0){
				Fu(i,2);
				li2.Add(new int[]{c[2],c[3]});
			}
		}
		if(!bo){
			Console.WriteLine(-1);
			return;
		}
		var bs=new Bitset(n+1);
		bs[li2[0][0]]=bs[li2[0][1]]=1;
		for(int i = 1;i<li2.Count;i++) {
			Array.Sort(li2[i]);
			bs<<=li2[i][0];
			bs|=bs<<=li2[i][1]-li2[i][0];
		}
		long ans=long.MaxValue;
		for(int i = 0;i<=n;i++) {
			if(bs[i]==1){
				ans=Min(ans,(((long)n-i)*(n-i-1)>>1)+(((long)i)*(i-1)>>1));
			}
		}
		Console.WriteLine("{0}",ans);
	}
	static void Fu(int a,int g){
		b[a]=g;
		c[g]++;
		for(int i=1;i<=n&&bo;i++){
			if(h[a][i]==1||a==i){continue;}
			if(b[i]==b[a]){
				bo=false;
				break;
			}
			if(b[i]==0){Fu(i,g^1);}
		}
	}
}
public class Bitset{
	public int n,l;
	public ulong[] he;
	public Bitset(int n){
		this.n=n;
		l=(n>>6)+1;
		he=new ulong[l];
	}
	public Bitset(int n,long a){
		this.n=n;
		l=(n>>6)+1;
		he=new ulong[l];
		he[0]=(ulong)a;
	}
	public Bitset(int n,bool b){
		this.n=n;
		l=(n>>6)+1;
		he=new ulong[l];
		int y=n%64;
		if(y==0){for(int i = 0;i<l;i++) {he[i]=ulong.MaxValue;}}
		else{
			for(int i = 0;i<l-1;i++) {he[i]=ulong.MaxValue;}
			he[l-1]=(1UL<<y)-1;
		}
	}
	public Bitset(Bitset b){
		n=b.n;
		l=b.l;
		he=new ulong[l];
		for(int i = 0;i<l;i++) {he[i]=b.he[i];}
	}
	public int this[int i]{
		set{he[i>>6]=(he[i>>6]&(ulong.MaxValue^(1UL<<i)))|((ulong)value<<i);}
		get{return (int)((he[i>>6]>>i)&1);}
	}
	public static Bitset operator&(Bitset a,Bitset b){
		Bitset c=new Bitset(a.n);
		int d=Math.Min(a.l,b.l);
		for(int i=0;i<d;i++){c.he[i]=a.he[i]&b.he[i];}
		return c;
	}
	public static Bitset operator|(Bitset a,Bitset b){
		Bitset c;
		if(a.l<b.l){c=a;a=b;b=c;}
		c=new Bitset(a.n);
		int i=0;
		for(;i<b.l;i++){c.he[i]=a.he[i]|b.he[i];}
		for(;i<a.l;i++){c.he[i]=a.he[i];}
		return c;
	}
	public static Bitset operator^(Bitset a,Bitset b){
		Bitset c;
		if(a.l<b.l){c=a;a=b;b=c;}
		c=new Bitset(a.n);
		int i=0;
		for(;i<b.l;i++){c.he[i]=a.he[i]^b.he[i];}
		for(;i<a.l;i++){c.he[i]=a.he[i];}
		return c;
	}
	public static Bitset operator<<(Bitset a,int b){
		Bitset c=new Bitset(a.n);
		if(b>a.l<<6){return c;}
		int d=(b+63)>>6;
		if(b%64==0){for(int i=a.l-1;i>=d;i--){c.he[i]=a.he[i-d];}}
		else{
			for(int i=a.l-1;i>=d;i--){c.he[i]=(a.he[i-d+1]<<b)|(a.he[i-d]>>(64-b));}
			c.he[d-1]=a.he[0]<<b;
		}
		return c;
	}
	public static Bitset operator>>(Bitset a,int b){
		Bitset c=new Bitset(a.n);
		if(b>a.l<<6){return c;}
		int d=(b+63)>>6;
		if(b%64==0){for(int i=0;i+d<c.l;i++){c.he[i]=a.he[i+d];}}
		else{
			for(int i=0;i+d<c.l;i++){c.he[i]=(a.he[i+d-1]>>b)|(a.he[i+d]<<(64-b));}
			c.he[c.l-d]=a.he[c.l-1]>>b;
		}
		return c;
	}
	public static bool operator==(Bitset a,Bitset b){
		int mx=Max(a.l,b.l),mn=Min(a.l,b.l);
		for(int i=0;i<mn;i++){if(a.he[i]!=b.he[i]){return false;}}
		if(a.l>b.l){for(int i=mn;i<mx;i++){if(a.he[i]!=0){return false;}}}
		else{for(int i=mn;i<mx;i++){if(b.he[i]!=0){return false;}}}
		return true;
	}
	public static bool operator!=(Bitset a,Bitset b){
		int mx=Max(a.l,b.l),mn=Min(a.l,b.l);
		for(int i=0;i<mn;i++){if(a.he[i]!=b.he[i]){return true;}}
		if(a.l>b.l){for(int i=mn;i<mx;i++){if(a.he[i]!=0){return true;}}}
		else{for(int i=mn;i<mx;i++){if(b.he[i]!=0){return true;}}}
		return false;
	}
	public override bool Equals(object obj){return false;}
	public override int GetHashCode(){return 0;}
	public int cnt{get{
		int p=0;
		for(int i=0;i<l;i++){
			var bits=he[i];
			bits=(bits&0x5555555555555555)+(bits>>1&0x5555555555555555);
			bits=(bits&0x3333333333333333)+(bits>>2&0x3333333333333333);
			bits=(bits&0x0f0f0f0f0f0f0f0f)+(bits>>4&0x0f0f0f0f0f0f0f0f);
			bits=(bits&0x00ff00ff00ff00ff)+(bits>>8&0x00ff00ff00ff00ff);
			bits=(bits&0x0000ffff0000ffff)+(bits>>16&0x0000ffff0000ffff);
			p+=(int)((bits&0x00000000ffffffff)+(bits>>32&0x00000000ffffffff));
		}
		return p;
	}}
	public string St{get{
		string t="",s="";
		for(int i = 0;i<l-1;i++) {
			s=Convert.ToString((long)he[i],2);
			s=(64>s.Length?new string('0',64-s.Length):"")+s;
			t=s+t;
		}
		if(n%64!=0){
			s=Convert.ToString((long)he[l-1],2);
			s=((n%64)>s.Length?new string('0',(n%64)-s.Length):"")+s;
			return s+t;
		}
		return t;
	}}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 20252