#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <vector>
#include <cstdint>

struct GraphEdge {
	int from = 0;
	int to = 0;

	GraphEdge() = default;
	GraphEdge(int from, int to);
};

class Graph {
public:
	using EdgeID = int;
	using Edge = GraphEdge;
	using List = std::vector<EdgeID>;

private:
	std::vector<List> ids_m;
 	std::vector<Edge> edges_m;

public:
	Graph() = default;
	Graph(Graph&&) = default;
	Graph(const Graph&) = default;
	Graph& operator=(Graph&&) = default;
	Graph& operator=(const Graph&) = default;

	Graph(int size);
	int size() const;
	void init(int new_size);
	void reserve(int edge_count);
	
	void add(int from, int to);
	const Edge& getEdge(EdgeID id) const;
	const List& row(int from) const;

	Graph createReversedGraph() const;
};

#endif

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

#include <cassert>

GraphEdge::GraphEdge(int from, int to)
	: from(from), to(to) {
}

Graph::Graph(int size) 
	: ids_m(size) {
}

int Graph::size() const {
	return ids_m.size();
}

void Graph::init(int new_size) {
	assert(new_size >= size());
	ids_m.resize(new_size);
}

void Graph::reserve(int edge_count) {
	edges_m.reserve(edge_count);
}

void Graph::add(int from, int to) {
	ids_m[from].push_back(edges_m.size());
	edges_m.push_back(Edge(from, to));
}

const Graph::Edge& Graph::getEdge(EdgeID id) const {
	assert(id >= 0 && id < edges_m.size());
	return edges_m[id];
}

const Graph::List& Graph::row(int from) const {
	return ids_m[from];
}

/* 辺の向きを逆転させたグラフを作成 */
Graph Graph::createReversedGraph() const {
	Graph ret(size());
	ret.reserve(edges_m.size());

	for (const auto& edge : edges_m) {
		ret.add(edge.to, edge.from);
	}
	return ret;
}

#ifndef __GRAPH_UTIL_H__
#define __GRAPH_UTIL_H__

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif


bool isBipartite(const Graph& graph);
std::vector<bool> colorBipartiteGraph(const Graph& graph);
bool isBipartiteSub(const Graph& graph, std::vector<bool>& coloring);

std::vector<std::vector<int>> connectedComponents(const Graph& graph);

#endif

#ifdef ONLY_MY_ENVIR
#include "GraphUtil.h"
#endif

#include <cassert>
#include <stack>

/* 無向グラフの二部グラフ判定 O(n + m) */
bool isBipartite(const Graph& graph) {
	std::vector<bool> coloring(graph.size());
	return isBipartiteSub(graph, coloring);
}

/* 二部グラフとなるような頂点の分割を一つ見つける O(n + m) */
/* 戻り値: 頂点 -> 組 { 0, 1 } */
std::vector<bool> colorBipartiteGraph(const Graph& graph) {
	std::vector<bool> coloring(graph.size());
	bool succeeded = isBipartiteSub(graph, coloring);
	assert(succeeded);
	return coloring;
}

/* 戻り値: (bool, coloring) = (二部グラフかどうか, 二部グラフのときの塗り分け) */
bool isBipartiteSub(const Graph& graph, std::vector<bool>& coloring) {
	assert(graph.size() == coloring.size());

	struct State {
		int vertex;
		bool color;
		State(int vertex, bool color)
			: vertex(vertex), color(color) {
		}
	};

	const int size = graph.size();
	std::vector<bool> visited(size);
	for (int from = 0; from < size; ++from) {
		if (visited[from]) continue;

		std::stack<State> stack;
		stack.push(State(from, false));
		while (!stack.empty()) {
			const State state = stack.top();
			stack.pop();

			int from = state.vertex;
			bool color = state.color;
			if (visited[from]) {
				if (coloring[from] != color) return false;
				continue;
			}

			visited[from] = true;
			coloring[from] = color;

			for (auto id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				int to = edge.to;
				stack.push(State(to, !color));
			}
		}
	}
	return true;
}

/* 連結成分分解 O(n + m) */
std::vector<std::vector<int>> connectedComponents(const Graph& graph) {
	std::vector<std::vector<int>> groups;

	const int size = graph.size();
	std::vector<bool> visited(size);
	
	auto search = [&graph, &visited](int start, std::vector<int>& group) -> void {
		std::stack<int> stack;
		stack.push(start);
		while (!stack.empty()) {
			int from = stack.top();
			stack.pop();

			if (visited[from]) continue;
			visited[from] = true;
			group.push_back(from);

			for (auto id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				int to = edge.to;
				stack.push(to);
			}
		}
	};

	for (int from = 0; from < size; ++from) {
		if (visited[from]) continue;

		std::vector<int> group;
		search(from, group);
		groups.push_back(std::move(group));
	}

	return groups;
}
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <array>

#ifdef ONLY_MY_ENVIR
#include "Shortest.h"
#include "SpanningTree.h"
#include "GraphUtil.h"
#endif

using namespace std;

const int MAX = 700;
using Bits = bitset<2 * MAX + 1>;
bool A[MAX][MAX];
int main() {
	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			A[i][j] = i != j;
		}
	}

	for (int j = 0; j < m; ++j) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		A[a][b] = false;
		A[b][a] = false;
	}

	Graph g(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (A[i][j]) g.add(i, j);
		}
	}

	if (!isBipartite(g)) {
		cout << -1 << endl;
		return 0;
	}

	auto col = colorBipartiteGraph(g);

	std::vector<int> diffs;
	for (auto&& group : connectedComponents(g)) {
		int cnt = 0;
		for (int v : group) {
			cnt += col[v];
		}

		int diff = int(group.size()) - 2 * cnt;
		diffs.push_back(abs(diff));
	}

	Bits sum;
	sum[MAX] = true;
	for (int diff : diffs) {
		sum = (sum << diff) | (sum >> diff);
	}

	int mn;
	for (int i = 0; i <= n; ++i) {
		if (sum[MAX + i] || sum[MAX - i]) {
			mn = i;
			break;
		}
	}

	int a = (n + mn) / 2;
	int b = (n - mn) / 2;
	cout << a * (a - 1) / 2 + b * (b - 1) / 2 << endl;
	return 0;
}

Measured memory_bytes: 8272