#[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 ! biparate_dfs(n, edges, &mut xs, i, k) {
                return None;
            }
        }
    }
    return Some(xs);
}

fn biparate_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 ! biparate_dfs(n, edges, xs, to, k) {
                return false;
            }
        }
        else {
            if xs[to] == xs[i] {
                return false;
            }
        }
    }
    return true;
}

// minimize abs difference of (sum of x.0 or x.1) and reverse
fn select_dp(xs: Vec<(usize,usize)>) -> (usize,usize) {
    let mut total = 0;
    for &x in &xs {
        total += x.0 + x.1;
    }
    let mut dp = vec![false; total+1];
    dp[0] = true;
    for &x in &xs {
        for i in (0..total+1).rev() {
            if i >= x.0 && dp[i-x.0] {
                dp[i] = true;
            }
            else if i >= x.1 && dp[i-x.1] {
                dp[i] = true;
            }
            else {
                dp[i] = false;
            }
        }
    }
    let mut res = None;
    let mut diff = 0;
    for i in 0..total+1 {
        if total < i + i {
            break;
        }
        if dp[i] {
            if res.is_none() || diff > (total - i) - i {
                res = Some((i, total-i));
                diff = total - i - i;
            }
        }
    }
    match res {
        Some(a) => a,
        None => panic!(),
    }
}

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 (x,y) = select_dp(ys);
            let res = x*(x-1)/2 + y*(y-1)/2;
            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