using System;
using System.Collections.Generic;

public class Program
{
    private int N, M;
    private bool[][] Edge;

    // 探索済み
    private bool[] F;

    private List<int> List;


    public void Solve()
    {
        var sc = new Scanner();
        N = sc.NextInt();
        M = sc.NextInt();
        Edge = new bool[N][];
        for (int i = 0; i < N; i++)
        {
            Edge[i] = new bool[N];
        }

        for (int i = 0; i < M; i++)
        {
            int a = sc.NextInt() - 1;
            int b = sc.NextInt() - 1;
            Edge[a][b] = true;
            Edge[b][a] = true;
        }

        // 分け方自由
        if ((N - 1) * N / 2 == M)
        {
            int s = N / 2;
            int t = N - s;
            Console.WriteLine((s * (s - 1) + t * (t - 1)) / 2);
            return;
        }

        /*
         * 繋がっていない都市を別のグループにする
         * 二部グラフになる
         * 2つをどちらに割り当ててもOK
         * 2州の都市数の差が小さくなるようにする
         */
        F = new bool[N];
        List = new List<int>();

        for (int i = 0; i < N; i++)
        {
            if (!F[i])
            {
                List<int> a = new List<int>();
                List<int> b = new List<int>();
                if (!Search(i, a, b, true))
                {
                    Console.WriteLine("-1");
                    return;
                }

                List.Add(Math.Abs(a.Count - b.Count));
            }
        }

//        for (int i = 0; i < List.Count; i++)
//        {
//            Console.WriteLine($"{List[i].Item1} {List[i].Item2}");
//        }

        bool[] dp = new bool[701];
        dp[0] = true;
        foreach (int i in List)
        {
            bool[] next = new bool[701];
            for (int j = 0; j <= 700; j++)
            {
                if (dp[j])
                {
                    int p = j + i;
                    int m = Math.Abs(j - i);
                    next[p] = true;
                    next[m] = true;
                }
            }

            dp = next;
        }

        for (int i = 0; i <= 700; i++)
        {
            if (dp[i])
            {
                // t + s = N
                // t - s = i
                // 2t = N + i
                int t = (N + i) / 2;
                int s = N - t;
                Console.WriteLine((s * (s - 1) + t * (t - 1)) / 2);
                return;
            }
        }
    }


    private bool Search(int i, List<int> a, List<int> b, bool g)
    {
        if (g)
        {
            foreach (int j in a)
            {
                if (!Edge[i][j])
                {
                    return false;
                }
            }

            a.Add(i);
        }
        else
        {
            foreach (int j in b)
            {
                if (!Edge[i][j])
                {
                    return false;
                }
            }

            b.Add(i);
        }

        F[i] = true;

        for (int j = 0; j < N; j++)
        {
            if (F[j])
            {
                continue;
            }

            if (Edge[i][j])
            {
                continue;
            }

            if (!Search(j, a, b, !g))
            {
                return false;
            }
        }

        return true;
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

Measured memory_bytes: 17952