#[allow(unused_imports)]
use std::cmp::{min,max};
#[allow(unused_imports)]
use std::collections::BTreeMap;
#[allow(unused_imports)]
use std::ops::*;
#[allow(unused_imports)]
use std::collections::BinaryHeap;

fn biparate(n: usize, edges: &Vec<Vec<usize>>) -> Option<Vec<i64>> {
    let mut xs = vec![0; n];
    let mut k = 0;
    for i in 0..n {
        if xs[i] == 0 {
            k += 1;
            xs[i] = k;
            if ! dfs(n, edges, &mut xs, i, k) {
                return None;
            }
        }
    }
    return Some(xs);
}

fn dfs(n: usize, edges: &Vec<Vec<usize>>, xs: &mut Vec<i64>, i: usize, k: i64) -> bool {
    for &to in &edges[i] {
        if xs[to] == 0 {
            xs[to] = -1 * xs[i];
            if ! dfs(n, edges, xs, to, k) {
                return false;
            }
        }
        else {
            if xs[to] == xs[i] {
                return false;
            }
        }
    }
    return true;
}

fn main() {
    let (n,m) = {
        let xs = read_vec_i64();
        (xs[0] as usize, xs[1] as usize)
    };
    let edges = {
        let mut exist = vec![vec![false; n]; n];
        for i in 0..m {
            let ys = read_vec_i64();
            let a = (ys[0]-1) as usize;
            let b = (ys[1]-1) as usize;
            exist[a][b] = true;
            exist[b][a] = true;
        }
        let mut edges = vec![vec![]; n];
        for i in 0..n {
            for k in 0..n {
                if i == k { continue; }
                if ! exist[i][k] {
                    edges[i].push(k);
                }
            }
        }
        edges
    };
    if m * 2 == n * (n - 1) {
        let a = n / 2;
        let b = n - a;
        println!("{}", a*(a-1)/2 + b*(b-1)/2);
        return;
    }
    let bs = biparate(n, &edges);
    match bs {
        Some(xs) => {
            let mut ys = vec![(0,0); n+1];
            for &x in &xs {
                if x > 0 {
                    ys[x as usize].0 += 1;
                }
                else if x < 0 {
                    ys[(-x) as usize].1 += 1;
                }
            }
            let mut dp = vec![false; n+1];
            dp[0] = true;
            for &y in &ys {
                if y.0 == 0 && y.1 == 0 {
                    continue;
                }
                for i in (0..n+1).rev() {
                    if i >= y.0 && dp[i-y.0] {
                        dp[i] = true;
                    }
                    else if i >= y.1 && dp[i-y.1] {
                        dp[i] = true;
                    }
                    else {
                        dp[i] = false;
                    }
                }
            }
            let inf = 1usize << 60;
            let mut res = inf;
            for i in 0..n+1 {
                if dp[i] {
                    let x = i;
                    let y = n - i;
                    if x == 0 || y == 0 {
                        continue;
                    }
                    let t = x*(x-1)/2 + y*(y-1)/2;
                    res = min(res, t);
                }
            }
            println!("{}", res);
        }
        None => {
            println!("-1");
        }
    }
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    return ss.parse::<i64>().unwrap();
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let mut res = vec![];
    let ss = read_line();
    for ts in ss.split_whitespace() {
        let x = ts.parse::<i64>().unwrap();
        res.push(x);
    }
    return res;
}

use std::fmt::Display;
#[allow(dead_code)]
fn write_vec<T: Display>(xs: &Vec<T>) {
    if xs.len() == 0 {
        println!("");
        return;
    }
    print!("{}", xs[0]);
    for i in 1..xs.len() {
        print!(" {}", xs[i]);
    }
    println!("");
}


Measured memory_bytes: 10492