use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

type Weight = i32;
#[allow(dead_code)]
#[derive(Clone, Debug, Eq, PartialEq)]
struct Edge {
    index: usize,
    src: usize,
    dest: usize,
    weight: Weight,
}
#[allow(dead_code)]
impl Edge {
    fn new(index: usize, src: usize, dest: usize, weight: Weight) -> Edge {
        Edge {
            index: index,
            src: src,
            dest: dest,
            weight: weight,
        }
    }
}
impl std::cmp::Ord for Edge {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        (self.weight, self.src, self.dest).cmp(&(other.weight, other.src, other.dest))
    }
}
impl std::cmp::PartialOrd for Edge {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}
type Edges = Vec<Edge>;
type Graph = Vec<Edges>;
#[allow(dead_code)]
fn graph_new(n: usize) -> Graph {
    vec![vec![]; n]
}
#[allow(dead_code)]
fn add_bi_edge(graph: &mut Graph, index: &mut usize, src: usize, dest: usize, weight: Weight) {
    graph[src].push(Edge::new(*index, src, dest, weight));
    graph[dest].push(Edge::new(*index, dest, src, weight));
    *index += 1;
}
#[allow(dead_code)]
fn add_uni_edge(graph: &mut Graph, index: &mut usize, src: usize, dest: usize, weight: Weight) {
    graph[src].push(Edge::new(*index, src, dest, weight));
    *index += 1;
}

fn calc(
    memo: &mut Vec<Vec<i32>>,
    lr: &Vec<(usize, usize)>,
    depth: usize,
    l: usize,
    r: usize,
) -> i32 {
    if depth == lr.len() {
        return 0;
    }
    if memo[l][r] != -1 {
        return memo[l][r];
    }
    let cnts = vec![lr[depth].0, lr[depth].1];
    let mut ret = 0;
    for i in 0..2 {
        let nl = l + cnts[i];
        let nr = r + cnts[i ^ 1];
        let mut nret = (l * cnts[i ^ 1] + r * cnts[i]) as i32;
        nret += calc(memo, lr, depth + 1, nl, nr);
        ret = std::cmp::max(ret, nret);
    }
    memo[l][r] = ret;
    ret
}

fn main() {
    let n = read::<usize>();
    let m = read::<usize>();
    let mut matrix = vec![vec![false; n]; n];
    let mut g = graph_new(n);
    let mut e = 0;
    for _ in 0..m {
        let a = read::<usize>() - 1;
        let b = read::<usize>() - 1;
        add_bi_edge(&mut g, &mut e, a, b, 1);
        matrix[a][b] = true;
        matrix[b][a] = true;
    }
    if m == n * (n - 1) / 2 {
        let l = n / 2;
        let r = n - l;
        println!("{}", m - l * r);
        return;
    }
    let mut used = vec![false; n];
    let mut all = 0;
    let mut lr: Vec<(usize, usize)> = vec![];
    for i in 0..n {
        if g[i].len() == n - 1 {
            used[i] = true;
            all += 1;
        }
    }
    let mut cnt = 0;
    loop {
        let mut que = vec![];
        for i in 0..n {
            if used[i] {
                continue;
            }
            que.push((i, 0));
            break;
        }
        if que.len() == 0 {
            break;
        }
        let mut opens = vec![vec![]; 2];
        let mut visited = vec![false; n];
        while let Some((from, l)) = que.pop() {
            if visited[from] {
                continue;
            }
            opens[l].push(from);
            visited[from] = true;
            used[from] = true;
            for to in 0..n {
                if to == from || matrix[from][to] {
                    continue;
                }
                que.push((to, l ^ 1))
            }
        }
        assert!(opens[0].len() > 0);
        assert!(opens[1].len() > 0);
        lr.push((opens[0].len(), opens[1].len()));
        for i in 0..2 {
            for &a in opens[i].iter() {
                for &b in opens[i].iter() {
                    if a != b && !matrix[a][b] {
                        println!("{}", -1);
                        return;
                    }
                }
            }
        }
        for &a in opens[0].iter() {
            for &b in opens[1].iter() {
                if matrix[a][b] {
                    cnt += 1;
                }
            }
        }
        // println!("{:?}", opens);
    }
    for _ in 0..all {
        lr.push((1, 0));
    }
    let mut memo = vec![vec![-1; n + 1]; n + 1];
    let ans = m as i32 - (calc(&mut memo, &lr, 0, 0, 0) + cnt);
    println!("{}", ans);
}


Measured memory_bytes: 32816