// Author: Ivan Kazmenko (gassa@mail.ru)
module solution;
import std.algorithm;
import std.stdio;

void main ()
{
	int n, m;
	while (readf (" %s %s", &n, &m) > 0)
	{
		auto a = new bool [] [] (n, n);
		foreach (k; 0..m)
		{
			int u, v;
			readf (" %s %s", &u, &v);
			u -= 1;
			v -= 1;
			a[u][v] = true;
			a[v][u] = true;
		}

		auto c = new int [n];
		c[] = 2;
		int [2] d;

		bool recur (int v, int cur)
		{
			if (c[v] == cur)
			{
				return true;
			}
			if (c[v] != 2)
			{
				return false;
			}
			c[v] = cur;
			d[cur] += 1;
			foreach (u; 0..n)
			{
				if (u != v && !a[v][u])
				{
					if (!recur (u, !cur))
					{
						return false;
					}
				}
			}
			return true;
		}

		auto f = new bool [n + 1];
		f[0] = true;
		bool ok = true;
		foreach (v; 0..n)
		{
			if (c[v] == 2)
			{
				d = [0, 0];
				if (!recur (v, 0))
				{
					ok = false;
					break;
				}
				foreach_reverse (i; 0..n + 1)
				{
					if (f[i])
					{
						foreach (j; 0..2)
						{
							f[i + d[j]] = true;
	                                	}
	                                	if (d[].all)
	                                	{
	                                		f[i] = false;
	                                	}
					}
				}
			}
		}

		if (ok)
		{
			int res = int.max;
			foreach (i; 0..n + 1)
			{
				if (f[i])
				{
					int cur = 0;
					cur += i * (i - 1) / 2;
					cur += (n - i) * (n - i - 1) / 2;
					res = min (res, cur);
				}
			}
			writeln (res);
		}
		else
		{
			writeln (-1);
		}
	}
}
