#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <vector>
#include <cstdint>
#include <iostream>

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;
	int edgeCount() 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;
	const std::vector<Edge>& getEdges() const;
};

Graph inputGraph(bool directed = true, bool one_based = true, std::istream& ist = std::cin);

#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();
}

int Graph::edgeCount() const {
	return edges_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];
}

const std::vector<Graph::Edge>& Graph::getEdges() const {
	return edges_m;
}

Graph inputGraph(bool directed, bool one_based, std::istream& ist) {
	int n, m;
	ist >> n >> m;

	Graph ret(n);
	for (int j = 0; j < m; ++j) {
		int a, b;
		ist >> a >> b;
		if (one_based) {
			--a; --b;
		}

		if (directed) {
			ret.add(a, b);
		} else {
			ret.add(a, b);
			ret.add(b, a);
		}
	}
	return ret;
}
#ifndef __GRAPH_UTIL_H__
#define __GRAPH_UTIL_H__

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

Graph createReversedGraph(const Graph& graph);
Graph createComplementGraph(const Graph& graph);

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>


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

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

/* 補グラフを作成 O(n^2 + m) */
Graph createComplementGraph(const Graph& graph) {
	const int size = graph.size();
	std::vector<std::vector<bool>> matrix(size, std::vector<bool>(size, true));
	for (int i = 0; i < size; ++i) {
		matrix[i][i] = false;
	}

	for (const auto& edge : graph.getEdges()) {
		matrix[edge.to][edge.from] = false;
	}

	Graph ret(size);
	for (int i = 0; i < size; ++i) {
		for (int j = 0; j < size; ++j) {
			if (matrix[i][j]) {
				ret.add(i, j);
			}
		}
	}
	return ret;
}

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

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

/* out: (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) */
/* out: [各連結成分の頂点リスト] のリスト */
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() {
	Graph g = inputGraph(false);
	Graph h = createComplementGraph(g);

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

	const int n = h.size();
	auto col = colorBipartiteGraph(h);

	std::vector<int> diffs;
	for (auto&& group : connectedComponents(h)) {
		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: 8812