import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

int[][700] PS;
int[700] F1;
int[700] F2;

void main()
{
    auto nm = readln.split.to!(int[]);
    auto N = nm[0];
    auto M = nm[1];
    auto QS = new bool[][](N, N);
    foreach (_; 0..M) {
        auto ab = readln.split.to!(int[]);
        auto A = ab[0]-1;
        auto B = ab[1]-1;
        PS[A] ~= B;
        PS[B] ~= A;
        QS[A][B] = true;
        QS[B][A] = true;
    }

    F1[0] = 1;
    auto s = [0];
    auto ss = [0];
    while (!ss.empty) {
        auto h = ss[0];
        ss = ss[1..$];
        foreach (n; PS[h]) if (F1[n] != 1 && F1[n] != 2) {
            foreach (m; s) if (!QS[n][m]) goto ng1;
            F1[n] = 1;
            s ~= n;
            ss ~= n;
            continue;
            ng1:
            F1[n] = 2;
        }
    }

    F2[N-1] = 1;
    auto t = [N-1];
    ss = [N-1];
    while (!ss.empty) {
        auto h = ss[0];
        ss = ss[1..$];
        foreach (n; PS[h]) if (F2[n] != 1 && F2[n] != 2) {
            foreach (m; t) if (!QS[n][m]) goto ng2;
            F2[n] = 1;
            t ~= n;
            ss ~= n;
            continue;
            ng2:
            F2[n] = 2;
        }
    }

    foreach (i; 0..N) if (F1[i] != 1 && F2[i] != 1) {
        writeln(-1);
        return;
    }

    auto sc = s.length;
    auto tc = t.length;

    auto d = sc + tc - N;
    while (d) {
        if (sc > tc) {
            --sc;
        } else {
            --tc;
        }
        --d;
    }
    auto SS = new int[](N+1);
    foreach (int i; 1..N+1) {
        SS[i] = SS[i-1] + i;
    }

    writeln(SS[sc-1] + SS[tc-1]);
}