AtCoder Regular Contest 099 - Independence

In the State of Takahashi in AtCoderian Federation, there are N cities, numbered 1, 2, ..., N.
M bidirectional roads connect these cities.
The i-th road connects City A_i and City B_i.
Every road connects two distinct cities.
Also, for any two cities, there is at most one road that directly connects them.
One day, it was decided that the State of Takahashi would be divided into two states, Taka and Hashi.
After the division, each city in Takahashi would belong to either Taka or Hashi.
It is acceptable for all the cities to belong Taka, or for all the cities to belong Hashi.
Here, the following condition should be satisfied:
 - Any two cities in the same state, Taka or Hashi, are directly connected by a road.
Find the minimum possible number of roads whose endpoint cities belong to the same state.
If it is impossible to divide the cities into Taka and Hashi so that the condition is satisfied, print -1.

-----Constraints-----
 - 2 \leq N \leq 700
 - 0 \leq M \leq N(N-1)/2
 - 1 \leq A_i \leq N
 - 1 \leq B_i \leq N
 - A_i \neq B_i
 - If i \neq j, at least one of the following holds: A_i \neq A_j and B_i \neq B_j.
 - If i \neq j, at least one of the following holds: A_i \neq B_j and B_i \neq A_j.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1
A_2 B_2
:
A_M B_M

-----Output-----
Print the answer.

-----Sample Input-----
5 5
1 2
1 3
3 4
3 5
4 5

-----Sample Output-----
4

For example, if the cities 1, 2 belong to Taka and the cities 3, 4, 5 belong to Hashi, the condition is satisfied.
Here, the number of roads whose endpoint cities belong to the same state, is 4.

Difficulty: HARD

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class UnionFind:

	def __init__(self, n):
		self.state = [-1] * n
		self.size_table = [1] * n

	def root(self, u):
		v = self.state[u]
		if v < 0:
			return u
		self.state[u] = res = self.root(v)
		return res

	def merge(self, u, v):
		ru = self.root(u)
		rv = self.root(v)
		if ru == rv:
			return
		du = self.state[ru]
		dv = self.state[rv]
		if du > dv:
			(ru, rv) = (rv, ru)
		if du == dv:
			self.state[ru] -= 1
		self.state[rv] = ru
		self.size_table[ru] += self.size_table[rv]
		return

	def size(self, u):
		return self.size_table[self.root(u)]

def ng():
	for u in range(n):
		for v in range(n):
			if v == u:
				continue
			if to[u][v]:
				continue
			if uf.root(u) == uf.root(v):
				return True
	return False
(n, m) = MI()
to = [[False] * n for _ in range(n)]
for _ in range(m):
	(u, v) = MI1()
	to[u][v] = to[v][u] = True
uf = UnionFind(n)
uncon = [-1] * n
for u in range(n):
	pv = -1
	for v in range(n):
		if v == u:
			continue
		if to[u][v]:
			continue
		if pv == -1:
			pv = v
		else:
			uf.merge(pv, v)
	uncon[u] = pv
if ng():
	print(-1)
	return
fin = [False] * n
free = 0
ss = []
for u in range(n):
	if uncon[u] == -1:
		free += 1
		continue
	r0 = uf.root(u)
	if fin[r0]:
		continue
	r1 = uf.root(uncon[u])
	fin[r0] = fin[r1] = True
	ss.append(abs(uf.size_table[r0] - uf.size_table[r1]))
cur = 1 << 1000
for s in ss:
	cur = cur << s | cur >> s
cur >>= 1000
d = (cur & -cur).bit_length() - 1
d = max(0, d - free)
s0 = (n - d) // 2
s1 = n - s0
print(s0 * (s0 - 1) // 2 + s1 * (s1 - 1) // 2)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
(n, m) = map(int, input().split())
G = [[1] * n for i in range(n)]
for i in range(n):
	G[i][i] = 0
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a][b] = 0
	G[b][a] = 0
from collections import deque
used = [0] * n
tmp = []

def bfs(start):
	if used[start]:
		return True
	d = {-1: 0, 1: 0}
	que = deque()
	que.append((start, 1))
	while que:
		(cur, flag) = que.popleft()
		if used[cur] == flag:
			continue
		elif used[cur]:
			return False
		used[cur] = flag
		d[flag] += 1
		for to in range(n):
			if G[cur][to] and used[to] == 0:
				que.append((to, -flag))
	tmp.append(list(d.values()))
	return True
if not all((bfs(i) for i in range(n))):
	print(-1)
else:
	s = set([0])
	target = (n + 1) // 2
	for l in tmp:
		t = set()
		for a in l:
			for b in s:
				if a + b <= target:
					t.add(a + b)
		s = t
	k = max(s)
	l = n - k
	ans = k * (k - 1) // 2 + l * (l - 1) // 2
	print(ans)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul
sys.setrecursionlimit(2147483647)
INF = 10 ** 20

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(n, m) = LI()
G = [set(range(n)) for _ in range(n)]
for i in range(n):
	G[i].remove(i)
for _ in range(m):
	(a, b) = LI()
	G[a - 1].remove(b - 1)
	G[b - 1].remove(a - 1)
color = [0] * n

def bipartite_or_not(s):
	color[s] = 1
	dq = deque([s])
	b = 1
	w = 0
	while dq:
		u = dq.popleft()
		for v in G[u]:
			if color[v] and color[u] != color[v]:
				continue
			elif color[v] and color[u] == color[v]:
				print(-1)
				exit()
			color[v] = -color[u]
			if color[v] == 1:
				b += 1
			else:
				w += 1
			dq += [v]
	return (b, w)
bit = 1
for i in range(n):
	if color[i]:
		continue
	(p, q) = bipartite_or_not(i)
	bit = bit << p | bit << q
for j in range(n // 2, -1, -1):
	if bit >> j & 1:
		print(n * (n - 1) // 2 - j * (n - j))
		break


def main():
	from sys import stdin
	input = stdin.readline
	(n, m) = map(int, input().split())
	ab = [list(map(int, input().split())) for _ in [0] * m]
	rest = n
	g = [set() for _ in [0] * n]
	[g[a - 1].add(b - 1) for (a, b) in ab]
	[g[b - 1].add(a - 1) for (a, b) in ab]
	s = set([i for i in range(n)])
	(a_list, b_list) = ([], [])
	while True:
		if m == rest * (rest - 1) // 2:
			break
		a = [-1, 10 ** 10]
		for i in s:
			length = len(g[i])
			if length < a[1]:
				a = [i, length]
		a = a[0]
		b = [-1, 10 ** 10]
		for i in s - g[a] - {a}:
			length = len(g[i])
			if length < b[1]:
				b = [i, length]
		b = b[0]
		(a_set, b_set) = ({a}, {b})
		s.remove(a)
		s.remove(b)
		rest -= 2
		remain = set()
		for i in s:
			flag_a = True
			for j in a_set:
				if j not in g[i]:
					flag_a = False
				else:
					g[i].remove(j)
					g[j].remove(i)
					m -= 1
			flag_b = True
			for j in b_set:
				if j not in g[i]:
					flag_b = False
				else:
					g[i].remove(j)
					g[j].remove(i)
					m -= 1
			if flag_a + flag_b == 0:
				print(-1)
				return
			elif flag_a * flag_b == 0:
				q = {i}
				flag = flag_a
				while q:
					qq = set()
					while q:
						i = q.pop()
						if flag:
							a_set.add(i)
						else:
							b_set.add(i)
						for j in remain:
							if j not in g[i]:
								qq.add(j)
							else:
								g[i].remove(j)
								g[j].remove(i)
								m -= 1
						for j in q:
							g[i].remove(j)
							g[j].remove(i)
							m -= 1
					for i in qq:
						remain.remove(i)
					flag ^= True
					q = qq
			else:
				remain.add(i)
		for i in (a_set | b_set) - {a} - {b}:
			s.remove(i)
			rest -= 1
		a_list.append(len(a_set))
		b_list.append(len(b_set))
	k = len(a_list)
	dp = [False] * (n + 1)
	dp[0] = True
	for i in range(k):
		(a, b) = (a_list[i], b_list[i])
		dp2 = [False] * (n + 1)
		for j in range(n - max(a, b) + 1):
			dp2[j + a] |= dp[j]
			dp2[j + b] |= dp[j]
		dp = dp2
	ans = 10 ** 10
	for j in range(rest + 1):
		for i in range(n - j + 1):
			if dp[i]:
				p = i + j
				q = n - p
				ans = min(ans, p * (p - 1) // 2 + q * (q - 1) // 2)
	print(ans)
main()


(n, m) = list(map(int, input().split()))
road = {}
whole = []
for i in range(1, n + 1):
	whole.append(i)
	road[i] = set()
whole = set(whole)
for i in range(m):
	(a, b) = list(map(int, input().split()))
	road[a].add(b)
	road[b].add(a)
taka = []
hashi = []
used = set()
no = 0
for x in road:
	l = set()
	r = set()
	l1 = []
	r1 = []
	if x in used:
		continue
	else:
		l.add(x)
		l1.append(x)
		used.add(x)
		for y in whole - road[x]:
			if y not in used:
				r.add(y)
				r1.append(y)
				used.add(y)
	while l1 != [] or r1 != []:
		while r1 != []:
			t = r1.pop()
			for y in whole - road[t] - used - l:
				l.add(y)
				l1.append(y)
				used.add(y)
		while l1 != []:
			t = l1.pop()
			for y in whole - road[t] - used - r:
				r.add(y)
				r1.append(y)
				used.add(y)
	r = list(r)
	l = list(l)
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			if l[j] not in road[l[i]]:
				no = 1
				break
		if no == 1:
			break
	if no == 1:
		break
	for i in range(len(r)):
		for j in range(i + 1, len(r)):
			if r[j] not in road[r[i]]:
				no = 1
				break
		if no == 1:
			break
	if no == 1:
		break
	taka.append(len(l))
	hashi.append(len(r))
if no == 1:
	print(-1)
else:
	res = [abs(taka[i] - hashi[i]) for i in range(len(taka))]
	res.sort(reverse=-1)
	delta = 0
	for x in res:
		if delta > 0:
			delta -= x
		else:
			delta += x
	left = (n + delta) / 2
	right = (n - delta) / 2
	result = int((left * (left - 1) + right * (right - 1)) / 2)
	print(result)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
e = [set([x for x in range(1, N + 1) if i != x]) for i in range(N + 1)]
for _ in range(M):
	(u, v) = map(int, input().split())
	e[u].discard(v)
	e[v].discard(u)
cl = [0] * (N + 1)
dp = [0] * (N + 1)
dp[0] = 1
for x in range(1, N + 1):
	if cl[x]:
		continue
	s = [x]
	qs = []
	cl[x] = 1
	while len(s):
		p = s.pop()
		qs.append(p)
		for q in e[p]:
			if cl[q]:
				if cl[q] % 2 == cl[p] % 2:
					print(-1)
					return
				continue
			cl[q] = cl[p] % 2 + 1
			s.append(q)
	predp = dp[:]
	for i in range(N, -1, -1):
		if dp[i] == 0:
			continue
		u = 0
		v = 0
		for q in qs:
			u += cl[q] % 2
			v += cl[q] % 2 == 0
		dp[i] -= predp[i]
		dp[i + u] += 1
		dp[i + v] += 1
res = N * (N - 1) // 2
for i in range(1, N + 1):
	if dp[i] == 0:
		continue
	u = i * (i - 1) // 2
	v = (N - i) * (N - i - 1) // 2
	res = min(res, u + v)
print(res)


import itertools
import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(N, M) = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
edges = set()
for (a, b) in AB:
	a -= 1
	b -= 1
	edges.add((a, b))
	edges.add((b, a))
graph = [[] for _ in range(N)]
for (a, b) in itertools.combinations(range(N), r=2):
	if (a, b) not in edges:
		graph[a].append(b)
		graph[b].append(a)
ok = True
pairs = []
seen = [False] * N
for v in range(N):
	if seen[v]:
		continue
	evens = {v}
	odds = set()
	stack = [(v, True)]
	while stack:
		(v, v_is_even) = stack.pop()
		next_set = odds if v_is_even else evens
		for u in graph[v]:
			if u in next_set:
				continue
			next_set.add(u)
			stack.append((u, not v_is_even))
	if len(evens) + len(odds) != len(evens | odds):
		ok = False
		break
	pairs.append((len(evens), len(odds)))
	for v in evens:
		seen[v] = True
	for v in odds:
		seen[v] = True
if not ok:
	print(-1)
	exit()
can_make = [[False] * (N + 1) for _ in range(len(pairs) + 1)]
can_make[0][0] = True
for (pi, (a, b)) in enumerate(pairs):
	for i in range(N + 1):
		if can_make[pi][i]:
			can_make[pi + 1][i + a] |= True
			can_make[pi + 1][i + b] |= True
ans = INF
for n in range(len(can_make[-1])):
	if can_make[-1][n]:
		m = N - n
		a = m * (m - 1) // 2
		b = n * (n - 1) // 2
		ans = min(ans, a + b)
print(ans)


(N, M) = map(int, input().split())
E = [[] for _ in range(N + 1)]
E_mat = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	E[a].append(b)
	E[b].append(a)
	E_mat[a][b] = 1
	E_mat[b][a] = 1
E_inv = [[] for _ in range(N + 1)]
for (v, e_mat) in enumerate(E_mat[1:], 1):
	for (u, e) in enumerate(e_mat[1:], 1):
		if e == 0 and v != u:
			E_inv[v].append(u)
colors = [0] * (N + 1)

def dfs(v, c):
	colors[v] = c
	cnts[c] += 1
	for u in E_inv[v]:
		if colors[u] == c:
			print(-1)
			exit()
		if colors[u] != 0:
			continue
		dfs(u, -c)
K = []
for v in range(1, N + 1):
	cnts = [0, 0, 0]
	if colors[v] == 0:
		dfs(v, 1)
	K.append(cnts[1:])
dp = 1
for (a, b) in K:
	dp = dp << a | dp << b
dp = bin(dp)[:1:-1]
ans = 0
mi = float('inf')
for (i, c) in enumerate(dp):
	if c == '1':
		if mi > abs(N / 2 - i):
			mi = abs(N / 2 - i)
			ans = i
print(ans * (ans - 1) // 2 + (N - ans) * (N - ans - 1) // 2)


from collections import deque
import numpy as np
(N, M) = map(int, input().split())
G = dict()
for i in range(1, N + 1):
	G[i] = dict()
	for j in range(1, N + 1):
		if i != j:
			G[i][j] = 1
for _ in range(M):
	(a, b) = map(int, input().split())
	_ = G[a].pop(b)
	_ = G[b].pop(a)
res_con = []
done_list = [1] + [0] * N
core = 1
while core != 0:
	queue = deque([core])
	res_flag = True
	size_a = 1
	size_b = 0
	done_list[core] = 1
	while len(queue) > 0:
		a = queue.popleft()
		for b in G[a].keys():
			if done_list[b] == done_list[a]:
				res_flag = False
				break
			elif done_list[b] == 0:
				done_list[b] = -1 * done_list[a]
				if done_list[a] == 1:
					size_b += 1
				else:
					size_a += 1
				queue.append(b)
	res_con.append([size_a, size_b])
	if res_flag == False:
		break
	core = 0
	for i in range(1, N + 1):
		if done_list[i] == 0:
			core = i
			break
if res_flag == False:
	res = 0
else:
	res_can_s = np.array([0])
	for rr in res_con:
		a = rr[0]
		b = rr[1]
		res_can_s = np.unique(np.concatenate([res_can_s + a, res_can_s + b]))
	res = (res_can_s * (res_can_s - 1) // 2 + (N - res_can_s) * (N - res_can_s - 1) // 2).min()
if res_flag == False:
	print(-1)
else:
	print(res)


from typing import List

class UnionFind:

	def __init__(self, n: int) -> None:
		self.p = [-1] * n
		self.rank = [1] * n
		self.size = [1] * n

	def find(self, x: int) -> int:
		if self.p[x] == -1:
			return x
		else:
			self.p[x] = self.find(self.p[x])
			return self.p[x]

	def unite(self, x: int, y: int) -> bool:
		if not self.same(x, y):
			x = self.find(x)
			y = self.find(y)
			if self.rank[x] > self.rank[y]:
				(x, y) = (y, x)
			elif self.rank[x] == self.rank[y]:
				self.rank[y] += 1
			self.p[x] = y
			self.size[y] += self.size[x]
			return True
		else:
			return False

	def same(self, x: int, y: int) -> bool:
		return self.find(x) == self.find(y)
(n, m) = list(map(int, input().split()))
path = [[1] * n for _ in range(n)]
for j in range(n):
	path[j][j] = 0
for i in range(m):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	path[a][b] = 0
	path[b][a] = 0
uf = UnionFind(2 * n)
for i in range(n):
	for j in range(n):
		if path[i][j] == 1:
			uf.unite(i, j + n)
			uf.unite(i + n, j)
for i in range(n):
	if uf.same(i, i + n):
		print(-1)
		return
deltas: List[int] = []
view = [1] * n
for i in range(n):
	if view[i] == 0:
		continue
	delta = 0
	for j in range(n):
		if uf.same(i, j):
			view[j] = 0
			delta += 1
		elif uf.same(i, j + n):
			view[j] = 0
			delta -= 1
	delta = abs(delta)
	deltas.append(delta)
dp = [0] * (n + 10)
dp[0] = 1
for delta in deltas:
	dpnxt = [0] * (n + 10)
	for i in range(n + 1):
		if i + delta <= n:
			dpnxt[i + delta] += dp[i]
		dpnxt[abs(i - delta)] += dp[i]
	dp = dpnxt.copy()
for i in range(n + 1):
	if dp[i]:
		print((n + i) // 2 * ((n + i - 1) // 2) // 2 + (n - i) // 2 * ((n - i - 1) // 2) // 2)
		return


(N, M) = map(int, input().split())
E = [[False] * N for _ in range(N)]
for n in range(N):
	E[n][n] = True
for _ in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	E[a][b] = True
	E[b][a] = True
unvisited = set(range(N))
color = [None] * N
components = []
while unvisited:
	v0 = next(iter(unvisited))
	count = [0, 0]
	stack = [(v0, False)]
	while stack:
		(v, c) = stack.pop()
		if color[v] is None:
			color[v] = c
			unvisited.discard(v)
			count[c] += 1
			for (u, f) in enumerate(E[v]):
				if not f:
					stack.append((u, not c))
		elif color[v] != c:
			print(-1)
			exit()
	components.append(count)
L = N // 2 + 1
dp = [False] * L
dp[0] = True
for (a, b) in components:
	ndp = [False] * L
	for (i, f) in enumerate(dp):
		if f:
			if i + a < L:
				ndp[i + a] = True
			if i + b < L:
				ndp[i + b] = True
	dp = ndp
for (i, f) in zip(reversed(range(L)), reversed(dp)):
	if f:
		break
j = N - i
print(i * (i - 1) // 2 + j * (j - 1) // 2)


import sys
(n, m) = list(map(int, input().split()))
N = 2000
G = [[0] * N for i in range(N)]
dp = [[0] * N for i in range(N)]
col = [0] * N
cnt = [0] * 2
visit = [0] * N
for i in range(m):
	(a, b) = list(map(int, input().split()))
	(a, b) = (a - 1, b - 1)
	(G[a][b], G[b][a]) = (1, 1)

def dfs(u, c):
	visit[u] = 1
	col[u] = c
	cnt[c] += 1
	for v in range(n):
		if v == u or G[u][v] == 1:
			continue
		if visit[v] == 1 and col[v] == c:
			return False
		if not visit[v] and (not dfs(v, c ^ 1)):
			return False
	return True
num = 0
dp[0][0] = 1
for i in range(n):
	if not visit[i]:
		num += 1
		(cnt[0], cnt[1]) = (0, 0)
		if not dfs(i, 0):
			print(-1)
			return
		for j in range(n):
			for k in range(2):
				if j >= cnt[k]:
					dp[num][j] |= dp[num - 1][j - cnt[k]]
ans = m
for i in range(n):
	if dp[num][i]:
		ans = min(ans, i * (i - 1) // 2 + (n - i) * (n - i - 1) // 2)
print(ans)


(N, M) = list(map(int, input().split()))
edge = [set([]) for i in range(N)]
for i in range(M):
	(a, b) = list(map(int, input().split()))
	edge[a - 1].add(b - 1)
	edge[b - 1].add(a - 1)
cedge = [[] for i in range(N)]
for i in range(N):
	for j in range(N):
		if j not in edge[i] and j != i:
			cedge[i].append(j)
ans = []

def is_bipartgraph():
	color = [0] * N
	used = [False] * N
	for i in range(N):
		if not used[i]:
			stack = [(i, 1)]
			black = 0
			white = 0
			while stack:
				(v, c) = stack.pop()
				color[v] = c
				black += (not used[v]) * (c == 1)
				white += (not used[v]) * (c == -1)
				used[v] = True
				for nv in cedge[v]:
					if color[nv] == color[v]:
						return False
					elif color[nv] == 0:
						stack.append((nv, -c))
			ans.append([black, white])
	return True
if is_bipartgraph():
	dp = [[False for i in range(0, N + 1)] for j in range(len(ans))]
	(a, b) = ans[0]
	(dp[0][a], dp[0][b]) = (True, True)
	for i in range(1, len(ans)):
		(a, b) = ans[i]
		for j in range(0, N + 1):
			test = False
			if j >= a:
				test = test | dp[i - 1][j - a]
			if j >= b:
				test = test | dp[i - 1][j - b]
			dp[i][j] = test
	ans = 0
	for i in range(0, N + 1):
		if dp[-1][i] and abs(ans - N / 2) > abs(i - N / 2):
			ans = i
	ans2 = N - ans
	print(ans * (ans - 1) // 2 + ans2 * (ans2 - 1) // 2)
else:
	print(-1)


from collections import deque
(N, M) = list(map(int, input().split()))
adjL = [set(range(N)) for _ in range(N)]
for v in range(N):
	adjL[v].remove(v)
for _ in range(M):
	(A, B) = list(map(int, input().split()))
	(A, B) = (A - 1, B - 1)
	adjL[A].remove(B)
	adjL[B].remove(A)

def getSizes(adjList):

	def bfs(vSt):
		colors[vSt] = 1
		nums[1] += 1
		Q = deque([vSt])
		while Q:
			vNow = Q.popleft()
			color = colors[vNow]
			for v2 in adjList[vNow]:
				if colors[v2] == color:
					return False
				elif colors[v2] == 0:
					colors[v2] = -color
					nums[-color] += 1
					Q.append(v2)
		return True
	numV = len(adjList)
	colors = [0] * numV
	anss = []
	for vSt in range(numV):
		if colors[vSt] != 0:
			continue
		nums = {-1: 0, 1: 0}
		if not bfs(vSt):
			return []
		anss.append((nums[-1], nums[1]))
	return anss
sizes = getSizes(adjL)
if not sizes:
	print(-1)
else:
	bitset = 1 << N
	for (A, B) in sizes:
		bitset = bitset >> A | bitset >> B
	minDiff = N
	iMinDiff = -1
	for i in reversed(list(range(N + 1))):
		if bitset & 1:
			diff = abs(i - N / 2)
			if diff < minDiff:
				minDiff = diff
				iMinDiff = i
		bitset >>= 1
	print(iMinDiff * (iMinDiff - 1) // 2 + (N - iMinDiff) * (N - iMinDiff - 1) // 2)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, m) = list(map(int, input().split()))
mt = [[True] * n for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	mt[a][b] = False
	mt[b][a] = False
for i in range(n):
	mt[i][i] = False
ns = [[] for _ in range(n)]
for i in range(n):
	for j in range(n):
		if mt[i][j]:
			ns[i].append(j)

def is_bip(ns):
	cs = [None] * n
	vs = []
	for start in range(n):
		if cs[start] is not None:
			continue
		v0 = v1 = 0
		q = [start]
		cs[start] = 1
		v1 += 1
		while q:
			u = q.pop()
			c = cs[u]
			cc = int(not c)
			for v in ns[u]:
				if cs[v] is None:
					cs[v] = cc
					if cc == 0:
						v0 += 1
					else:
						v1 += 1
					q.append(v)
				elif cs[v] == c:
					return (False, None)
		vs.append((v0, v1))
	return (True, vs)
(res, vs) = is_bip(ns)
if not res:
	ans = -1
else:
	dp = 1
	for (v0, v1) in vs:
		dp = dp << v0 | dp << v1
	ans = float('inf')
	for i in range(1, n + 1):
		if dp >> i & 1:
			ans = min(ans, i * (i - 1) // 2 + (n - i) * (n - i - 1) // 2)
print(ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
graph1 = [[False] * N for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	graph1[a - 1][b - 1] = True
	graph1[b - 1][a - 1] = True
graph = [[] for _ in range(N)]
for i in range(N):
	for j in range(N):
		if i != j and (not graph1[i][j]):
			graph[i].append(j)
checked = [-1] * N
Color = [None] * N

def bfs(start):
	q = [start]
	checked[start] = start
	Color[start] = 0
	color = 0
	Cs = [1, 0]
	while q:
		qq = []
		color ^= 1
		for p in q:
			for np in graph[p]:
				if checked[np] == -1:
					checked[np] = start
					Color[np] = color
					qq.append(np)
					Cs[color] += 1
				elif checked[np] == start and color != Color[np]:
					return [-1, -1]
		q = qq
	return Cs

def main():
	Dif = []
	for i in range(N):
		if checked[i] == -1:
			(a, b) = bfs(i)
			if a == -1:
				print(-1)
				return
			Dif.append(abs(a - b))
	dp = [False] * (N + 1)
	dp[0] = True
	for d in Dif:
		for j in reversed(range(d, N + 1)):
			dp[j] = dp[j] or dp[j - d]
	min_dif = 10 ** 15
	S = sum(Dif)
	for j in range(N + 1):
		if dp[j]:
			min_dif = min(min_dif, abs(S - j * 2))
	t1 = (N + min_dif) // 2
	t2 = (N - min_dif) // 2
	print(t1 * (t1 - 1) // 2 + t2 * (t2 - 1) // 2)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
G = [set() for _ in range(N)]
for _ in range(M):
	(A, B) = map(int, input().split())
	A -= 1
	B -= 1
	G[A].add(B)
	G[B].add(A)
G_comp = [[] for _ in range(N)]
for i in range(N):
	for j in range(N):
		if i != j and j not in G[i]:
			G_comp[i].append(j)
color = [-1] * N
A = []
dp = set([0])
for i in range(N):
	if color[i] != -1:
		continue
	cnt = [1, 0]
	color[i] = 0
	stack = [i]
	while stack:
		v = stack.pop()
		for u in G_comp[v]:
			if color[u] == -1:
				color[u] = 1 - color[v]
				stack.append(u)
				cnt[color[u]] += 1
			if color[u] == color[v]:
				print(-1)
				return
	ndp = set()
	for a in dp:
		ndp.add(a + cnt[0])
		ndp.add(a + cnt[1])
	dp = ndp
ans = float('inf')
for a in dp:
	ans = min(ans, a * (a - 1) // 2 + (N - a) * (N - a - 1) // 2)
print(ans)


def main():
	(n, m) = list(map(int, input().split()))
	ab = [list(map(int, input().split())) for _ in [0] * m]
	n_hozon = n
	g = [set() for _ in [0] * n]
	[g[a - 1].add(b - 1) for (a, b) in ab]
	[g[b - 1].add(a - 1) for (a, b) in ab]
	s = set([i for i in range(n)])
	(a_list, b_list) = ([], [])
	while True:
		if m == n * (n - 1) // 2:
			break
		a = [-1, 10 ** 10]
		for i in s:
			l = len(g[i])
			if l < a[1]:
				a = [i, l]
		a = a[0]
		b = [-1, 10 ** 10]
		for i in s - g[a] - {a}:
			l = len(g[i])
			if l < b[1]:
				b = [i, l]
		b = b[0]
		(a_set, b_set) = ({a}, {b})
		s.remove(a)
		s.remove(b)
		n -= 2
		remain = set()
		for i in s:
			flag_a = True
			for j in a_set:
				if j not in g[i]:
					flag_a = False
				else:
					g[i].remove(j)
					g[j].remove(i)
					m -= 1
			flag_b = True
			for j in b_set:
				if j not in g[i]:
					flag_b = False
				else:
					g[i].remove(j)
					g[j].remove(i)
					m -= 1
			if flag_a == flag_b == False:
				print(-1)
				return
			elif flag_a == False or flag_b == False:
				q = {i}
				flag = flag_a
				while q:
					qq = set()
					while q:
						i = q.pop()
						if flag:
							a_set.add(i)
						else:
							b_set.add(i)
						for j in remain:
							if j not in g[i]:
								qq.add(j)
							else:
								g[i].remove(j)
								g[j].remove(i)
								m -= 1
						for j in q:
							g[i].remove(j)
							g[j].remove(i)
							m -= 1
					for i in qq:
						remain.remove(i)
					flag ^= True
					q = qq
			else:
				remain.add(i)
		for i in (a_set | b_set) - {a} - {b}:
			s.remove(i)
			n -= 1
		a_list.append(len(a_set))
		b_list.append(len(b_set))
	m = n
	n = n_hozon
	k = len(a_list)
	if k == 1:
		dp = [False] * (n + 1)
		a = a_list[0]
		b = b_list[0]
		ans = 10 ** 10
		for i in range(m + 1):
			ans = min(ans, (a + i) * (a + i - 1) // 2 + (n - a - i) * (n - a - i - 1) // 2)
		print(ans)
		return
	dp = [False] * (n + 1)
	dp[0] = True
	for i in range(k):
		(a, b) = (a_list[i], b_list[i])
		maxab = max(a, b)
		dp2 = [False] * (n + 1)
		for j in range(n - maxab + 1):
			dp2[j + a] |= dp[j]
			dp2[j + b] |= dp[j]
		dp = dp2
	dp2 = [False] * (n + 1)
	for j in range(m + 1):
		for i in range(n - j + 1):
			dp2[i + j] |= dp[i]
	ans = 10 ** 10
	for i in range(n + 1):
		if dp2[i] is False:
			continue
		j = n - i
		ans = min(ans, i * (i - 1) // 2 + j * (j - 1) // 2)
	print(ans)
main()


from collections import deque
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
matrix = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = info[i]
	a -= 1
	b -= 1
	matrix[a][b] = 1
	matrix[b][a] = 1
graph = [[] for i in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		if matrix[i][j] == 0:
			graph[i].append(j)
			graph[j].append(i)

def coloring(graph):
	n = len(graph)
	visited = [-1] * n
	ans = []
	for i in range(n):
		if visited[i] >= 0:
			continue
		visited[i] = 0
		q = deque([i])
		num = [1, 0]
		while q:
			_from = q.pop()
			for to in graph[_from]:
				if visited[to] == visited[_from]:
					return [[-1, -1]]
				if visited[to] >= 0:
					continue
				visited[to] = visited[_from] ^ 1
				num[visited[to]] += 1
				q.append(to)
		ans.append(num)
	return ans
num = coloring(graph)
if num[0][0] == -1:
	print(-1)
	return
dp = [[False] * (n + 1) for _ in range(len(num) + 1)]
dp[0][0] = True
for i in range(len(num)):
	(a, b) = num[i]
	for j in range(n + 1):
		if j - a >= 0:
			dp[i + 1][j] = dp[i][j - a] or dp[i + 1][j]
		if j - b >= 0:
			dp[i + 1][j] = dp[i][j - b] or dp[i + 1][j]
ans = 10 ** 20
for (i, boolian) in enumerate(dp[len(num)]):
	if boolian:
		tmp_ans = i * (i - 1) // 2 + (n - i) * (n - i - 1) // 2
		ans = min(tmp_ans, ans)
print(ans)


from collections import deque
(N, M) = map(int, input().split())
G0 = [set([i]) for i in range(N)]
A = set(range(N))
for i in range(M):
	(a, b) = map(int, input().split())
	G0[a - 1].add(b - 1)
	G0[b - 1].add(a - 1)
G = [A - g for g in G0]
b = 1 << N // 2
c = [-1] * N
for i in range(N):
	if c[i] != -1:
		continue
	p = 0
	s = 0
	que = deque([i])
	c[i] = 0
	while que:
		v = que.popleft()
		s += 1
		if c[v] == 0:
			p += 1
		for w in G[v]:
			if c[w] == -1:
				c[w] = c[v] ^ 1
				que.append(w)
			elif c[w] == c[v]:
				print(-1)
				return
	b = b >> p | b >> s - p
p = N // 2 - ((b & -b).bit_length() - 1)
q = N - p
print(p * (p - 1) // 2 + q * (q - 1) // 2)


import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
	q = deque([s])
	color[s] = 1
	(w, b) = (1, 0)
	while q:
		v = q.popleft()
		for nv in G[v]:
			if color[nv] == 0:
				color[nv] = -color[v]
				q.append(nv)
				if color[nv] == 1:
					w += 1
				else:
					b += 1
			elif color[nv] == color[v]:
				return (-1, -1)
	return (w, b)
(N, M) = map(int, input().split())
A = [[0] * N for _ in range(N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	A[u - 1][v - 1] = 1
	A[v - 1][u - 1] = 1
G = [[] for _ in range(N)]
for i in range(N):
	for j in range(i + 1, N):
		if A[i][j] == 0:
			G[i].append(j)
			G[j].append(i)
color = [0] * N
(ws, bs) = ([], [])
for i in range(N):
	if color[i] == 0:
		(w, b) = bfs(i)
		if w == -1:
			print(-1)
			exit()
		ws.append(w)
		bs.append(b)
dp = [[False] * (N + 1) for _ in range(len(ws) + 1)]
dp[0][0] = True
for i in range(len(ws)):
	for j in range(N + 1):
		if j + ws[i] <= N:
			dp[i + 1][j + ws[i]] |= dp[i][j]
		if j + bs[i] <= N:
			dp[i + 1][j + bs[i]] |= dp[i][j]
ans = 10 ** 18
for i in range(N + 1):
	if dp[-1][i]:
		ans = min(ans, i * (i - 1) // 2 + (N - i) * (N - i - 1) // 2)
print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict
(N, M) = map(int, input().split())
rng = range(1, N + 1)
graph = [None] + [set((x for x in rng if x != y)) for y in rng]
for _ in range(M):
	(a, b) = map(int, input().split())
	graph[a].remove(b)
	graph[b].remove(a)
color = [None] * (1 + N)
size = defaultdict(lambda : [0, 0])

def set_color(root, x, c):
	size[root][c] += 1
	color[x] = c
	for y in graph[x]:
		if color[y] is None:
			set_color(root, y, 1 - c)
		elif color[y] == color[x]:
			print(-1)
			exit()
for x in rng:
	if color[x] is None:
		set_color(x, x, 0)
se = {0}
for (x, y) in size.values():
	se = set((s + x for s in se)) | set((s + y for s in se))
answer = min((x * (x - 1) // 2 + (N - x) * (N - x - 1) // 2 for x in se))
print(answer)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 998244353
dd = [(0, -1), (1, 0), (0, 1), (-1, 0)]
ddn = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, m) = LI()
	a = [LI_() for _ in range(m)]
	ss = [set() for _ in range(n)]
	for (b, c) in a:
		ss[b].add(c)
		ss[c].add(b)
	ts = [set(list(range(n))) - set([_]) for _ in range(n)]
	for i in range(n):
		ts[i] -= ss[i]
	d = []
	u = set()
	for i in range(n):
		if i in u:
			continue
		ab = set([i])
		nb = set([i])
		ac = set()
		nc = set()
		f = True
		while f:
			f = False
			k = set()
			nc = set()
			for j in nb:
				nc |= ts[j]
			nc -= ac
			ac |= nc
			nb = set()
			for j in nc:
				nb |= ts[j]
			nb -= ab
			ab |= nb
			if nb:
				f = True
		if ab & ac:
			return -1
		d.append((len(ab), len(ac)))
		u |= ab
		u |= ac
	r = set([0])
	for (b, c) in d:
		t = set()
		for k in r:
			t.add(k + b)
			t.add(k + c)
		r = t
	rr = inf
	for t in r:
		nt = n - t
		if t == 0 or nt == 0:
			continue
		tr = t * (t - 1) // 2
		tr += nt * (nt - 1) // 2
		if rr > tr:
			rr = tr
	return rr
print(main())


import sys
(N, M) = map(int, input().split())
data = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
	(A, B) = map(int, input().split())
	data[A][B] = 1
	data[B][A] = 1
for i in range(1, N + 1):
	data[i][i] = 1
lst = [-1] * (N + 1)
ddd = []
for i in range(1, N + 1):
	if lst[i] != -1:
		continue
	else:
		lst[i] = 0
		que = [i]
		count = [1, 0]
		while que:
			h = []
			for u in que:
				for j in range(1, N + 1):
					if data[u][j] == 1:
						continue
					elif lst[j] == -1:
						lst[j] = lst[u] ^ 1
						count[lst[j]] += 1
						h.append(j)
					elif lst[j] ^ lst[u] == 0:
						print(-1)
						sys.exit()
			que = h
		ddd.append(count)
dp = [0] * (N + 1)
dp[0] = 1
for u in ddd:
	v = u[0]
	h = [0] * (N + 1)
	for i in range(v, N + 1):
		if dp[i - v] == 1:
			h[i] = 1
	v = u[1]
	for i in range(v, N + 1):
		if dp[i - v] == 1:
			h[i] = 1
	dp = h
ans = 0
for i in range(N + 1):
	if dp[i] == 1:
		if abs(N - 2 * ans) > abs(N - 2 * i):
			ans = i
qqq = N - ans
if qqq == 0 or ans == 0:
	print(N * (N - 1) // 2)
else:
	print(ans * (ans - 1) // 2 + qqq * (qqq - 1) // 2)


(n, m, *A) = map(int, open(0).read().split())
g = [[1] * n for _ in [0] * n]
for (a, b) in zip(A[::2], A[1::2]):
	g[a - 1][b - 1] = g[b - 1][a - 1] = 0
U = [1] * n
D = 1

def dfs(v):
	nonlocal D
	R[U[v]] += 1
	for k in range(n):
		if g[v][k] * (k - v):
			D *= U[k] != U[v]
			if U[k] > 0:
				U[k] = ~U[v]
				dfs(k)
for i in range(n):
	if U[i] > 0:
		R = [0, 0]
		U[i] = 0
		dfs(i)
		D = D << R[0] | D << R[1]
a = -1
for i in range(n // 2 + 1):
	if D >> i & 1:
		a = (i * (i - 1) + (n - i) * (n - i - 1)) // 2
print(a)


(n, m) = map(int, input().split())
adjList = [[0] * n for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adjList[a][b] = 1
	adjList[b][a] = 1

def applyComp(a):
	for i in range(len(a)):
		for j in range(len(a[i])):
			a[i][j] = 1 - a[i][j]
applyComp(adjList)
visited = [0] * n

def dfs(u, parent=-1, color=1):
	if visited[u]:
		if visited[u] != color:
			print(-1)
			exit()
		return (0, 0)
	visited[u] = color
	oneCount = 0
	twoCount = 0
	if color == 1:
		oneCount += 1
	else:
		twoCount += 1
	for v in range(n):
		if u == v or u == parent:
			continue
		if adjList[u][v]:
			p = dfs(v, u, 3 - color)
			oneCount += p[0]
			twoCount += p[1]
	return (oneCount, twoCount)
connSize = []
for i in range(n):
	if visited[i]:
		continue
	connSize.append(dfs(i))
dp = [False] * (n + 1)
dp[0] = True
for (c1, c2) in connSize:
	ndp = [False] * (n + 1)
	for i in range(n + 1):
		if dp[i]:
			ndp[i + c1] = True
			ndp[i + c2] = True
	dp = ndp
print(min((sum((sz * (sz - 1) // 2 for sz in [sz1, n - sz1])) for sz1 in range(n + 1) if dp[sz1])))


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
(N, M) = reads()
orig_edges = set()
for _ in range(M):
	(A, B) = reads()
	(A, B) = (A - 1, B - 1)
	orig_edges.add((A, B))
	orig_edges.add((B, A))
edges = [[] for _ in range(N)]
for (A, B) in combinations(range(N), 2):
	if (A, B) not in orig_edges:
		edges[A].append(B)
		edges[B].append(A)
remain = set(range(N))
color = [-1] * N

def walk(u, c, ctr, remain):
	if u in remain:
		remain.remove(u)
	if color[u] >= 0:
		if color[u] != c:
			print(-1)
			exit()
		return ctr
	color[u] = c
	ctr[c] += 1
	for v in edges[u]:
		walk(v, 1 - c, ctr, remain)
	return ctr
ps = []
while len(remain) > 0:
	s = remain.pop()
	p = walk(s, 0, [0, 0], remain)
	ps.append(p)
dp = set([0])
for (a, b) in ps:
	d = b - a
	dp = {x - d for x in dp} | {x + d for x in dp}
m = min((abs(x) for x in dp))
(a, b) = ((N + m) // 2, (N - m) // 2)
print(a * (a - 1) // 2 + b * (b - 1) // 2)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
(n, m) = map(int, input().split())
G = [{i for i in range(n) if i != j} for j in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].remove(b)
	G[b].remove(a)
seen = [-1] * n
L = []

def is_bipartite(v, color):
	seen[v] = color
	L[-1][color] += 1
	for i in G[v]:
		if seen[i] != -1:
			if seen[i] == color:
				return False
		elif not is_bipartite(i, color ^ 1):
			return False
	return True
for i in range(n):
	if seen[i] == -1:
		L.append([0, 0])
		if not is_bipartite(i, 0):
			print(-1)
			break
else:
	dp = np.zeros((len(L) + 1, n + 1), dtype=bool)
	dp[0, 0] = True
	for (i, ab) in enumerate(L):
		(a, b) = ab
		dp[i + 1, a:] |= dp[i, :n + 1 - a]
		dp[i + 1, b:] |= dp[i, :n + 1 - b]
	temp = n // 2
	dp = dp[-1].tolist()
	while not dp[temp]:
		temp += 1
	r = n - temp
	print(temp * (temp - 1) // 2 + r * (r - 1) // 2)


import sys
readline = sys.stdin.readline
popcntsum = (1 << 1024) - 1
Fa = [0] + [popcntsum // ((1 << (1 << i - 1)) + 1) for i in range(1, 11)]
Fb = [0] + [Fa[i] << (1 << i - 1) for i in range(1, 11)]
fila1 = Fa[1]
filb1 = Fb[1]
fila2 = Fa[2]
filb2 = Fb[2]
fila3 = Fa[3]
filb3 = Fb[3]
fila4 = Fa[4]
filb4 = Fb[4]
fila5 = Fa[5]
filb5 = Fb[5]
fila6 = Fa[6]
filb6 = Fb[6]
fila7 = Fa[7]
filb7 = Fb[7]
fila8 = Fa[8]
filb8 = Fb[8]
fila9 = Fa[9]
filb9 = Fb[9]
fila10 = Fa[10]
filb10 = Fb[10]

def popcount(x):
	x = (x & fila1) + ((x & filb1) >> 1)
	x = (x & fila2) + ((x & filb2) >> 2)
	x = (x & fila3) + ((x & filb3) >> 4)
	x = (x & fila4) + ((x & filb4) >> 8)
	x = (x & fila5) + ((x & filb5) >> 16)
	x = (x & fila6) + ((x & filb6) >> 32)
	x = (x & fila7) + ((x & filb7) >> 64)
	x = (x & fila8) + ((x & filb8) >> 128)
	x = (x & fila9) + ((x & filb9) >> 256)
	x = (x & fila10) + ((x & filb10) >> 512)
	return x

def check(S):
	if S == 0:
		return []
	if S < 0:
		return None
	G1 = [G[i] & S for i in range(N)]
	M = popcount(S)
	if M ** 2 == sum((G1[i] for i in range(N) if S & 1 << i)):
		return [(0, 1)] * M
	st = 0
	A = 0
	for i in range(N):
		if 1 << i & S:
			st = i
			A = 1 << i
			break
	B = 0
	for i in range(N):
		if not 1 << i & S:
			continue
		if not G[st] & 1 << i:
			B = 1 << i
			break
	T = (1 << N) - 1 ^ S | A | B
	na = 1
	nb = popcount(B)
	T2 = None
	while T2 != T:
		T2 = T
		for i in range(N):
			if 1 << i & T:
				continue
			fa = na == popcount(G1[i] & A)
			fb = nb == popcount(G1[i] & B)
			if fa and fb:
				continue
			if fa:
				A |= 1 << i
				T |= 1 << i
				na += 1
				continue
			if fb:
				B |= 1 << i
				T |= 1 << i
				nb += 1
				continue
			return None
	S2 = (1 << N) - 1 ^ T
	if na > nb:
		(na, nb) = (nb, na)
	ss = check(S2)
	if ss is None:
		return None
	return ss + [(na, nb)]
(N, M) = map(int, readline().split())
G = [1 << i for i in range(N)]
for _ in range(M):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	G[a] |= 1 << b
	G[b] |= 1 << a
ss = check((1 << N) - 1)
if ss is None:
	print(-1)
else:
	(SA, SB) = list(map(list, zip(*ss)))
	res = 1
	for (sa, sb) in zip(SA, SB):
		res = res << sa | res << sb
	ans = 10 ** 9 + 7
	for i in range(N + 1):
		if not 1 << i & res:
			continue
		ans = min(ans, (i - 1) * i // 2 + (N - i - 1) * (N - i) // 2)
	print(ans)


def dfs(links, fixed, s):
	q = [(s, 0)]
	cnt = [0, 0]
	while q:
		(v, c) = q.pop()
		if fixed[v] > -1:
			if fixed[v] != c:
				return False
			continue
		fixed[v] = c
		cnt[c] += 1
		for u in links[v]:
			q.append((u, c ^ 1))
	return (max(cnt), min(cnt))

def is_bipartite(n, links):
	fixed = [-1] * n
	(l, r) = (0, 0)
	can = []
	for i in range(n):
		if fixed[i] > -1:
			continue
		cnt = dfs(links, fixed, i)
		if cnt == False:
			return -1
		can.append(cnt)
	can.sort(reverse=True)
	for cnt in can:
		j = 0 if cnt[0] > cnt[1] else 1
		if l > r:
			j ^= 1
		l += cnt[j]
		r += cnt[j ^ 1]
	return (l * (l - 1) + r * (r - 1)) // 2
(n, m) = list(map(int, input().split()))
links = [set(range(n)) - {i} for i in range(n)]
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	links[a].remove(b)
	links[b].remove(a)
print(is_bipartite(n, links))


from collections import deque
import sys
from operator import itemgetter
(N, M) = map(int, input().split())
table = [[1] * N for i in range(N)]
for i in range(N):
	table[i][i] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	table[a - 1][b - 1] = 0
	table[b - 1][a - 1] = 0
visit = [False] * N
color = [-1] * N

def f(i):
	q = deque()
	q.append(i)
	color[i] = 0
	visit[i] = True
	r = [0, 0]
	r[0] += 1
	while q:
		x = q.popleft()
		for j in range(N):
			if table[x][j] == 0:
				continue
			if visit[j]:
				if color[x] == color[j]:
					print(-1)
					sys.exit()
				continue
			q.append(j)
			color[j] = (color[x] + 1) % 2
			r[color[j]] += 1
			visit[j] = True
	return r
ans = []
for i in range(N):
	if not visit[i]:
		ans.append(f(i))
dp = [set() for i in range(len(ans) + 1)]
dp[0].add(0)
L = N // 2 + 1
for i in range(1, len(ans) + 1):
	for a in dp[i - 1]:
		if a + ans[i - 1][0] < L:
			dp[i].add(a + ans[i - 1][0])
		if a + ans[i - 1][1] < L:
			dp[i].add(a + ans[i - 1][1])
s = max(dp[len(ans)])

def dou(k):
	return k * (k - 1) // 2
print(dou(s) + dou(N - s))


import sys
input = sys.stdin.readline
from itertools import combinations
(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
g2d = [[1 for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
	g2d[i][i] = 0
for (a, b) in ab:
	g2d[a][b] = 0
	g2d[b][a] = 0
graph = [[] for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if g2d[i][j]:
			graph[i].append(j)
			graph[j].append(i)
vis = [-1] * (n + 1)
oddeven = []
for i in range(1, n + 1):
	if vis[i] == -1:
		stack = [i]
		vis[i] = 0
		odd = 0
		even = 1
		while stack:
			x = stack.pop()
			for y in graph[x]:
				if vis[y] == -1:
					vis[y] = vis[x] + 1
					if vis[y] % 2:
						odd += 1
					else:
						even += 1
					stack.append(y)
				elif (vis[y] - vis[x]) % 2 == 0:
					print(-1)
					exit()
		oddeven.append(abs(odd - even))
t = len(oddeven)
s = sum(oddeven)
dp = 1 << s
for x in oddeven:
	dp = dp << abs(x) | dp >> abs(x)
for i in range(s + 1):
	if dp & 1 << s - i | dp & 1 << s + i:
		ex = i
		break
(A, B) = ((n + ex) // 2, (n - ex) // 2)
print(A * (A - 1) // 2 + B * (B - 1) // 2)


from collections import Counter
import numpy as np

class DisjointSet:

	def __init__(self, size):
		self.parent = list(range(size))
		self.rank = [0] * size

	def find(self, x):
		stack = []
		parent = self.parent
		while parent[x] != x:
			stack.append(x)
			x = parent[x]
		for y in stack:
			parent[y] = x
		return x

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if self.rank[xr] > self.rank[yr]:
			self.parent[yr] = xr
		elif self.rank[xr] < self.rank[yr]:
			self.parent[xr] = yr
		elif xr != yr:
			self.parent[yr] = xr
			self.rank[xr] += 1

def check_bipartiteness(n_vertices, edges):
	ds = DisjointSet(2 * n_vertices)
	for (a, b) in edges:
		ds.union(a, b + n_vertices)
		ds.union(b, a + n_vertices)
	next_color = 0
	color = [-1] * (2 * n_vertices)
	for v in range(n_vertices):
		ra = ds.find(v)
		rb = ds.find(v + n_vertices)
		if ra == rb:
			return None
		if color[ra] < 0:
			color[ra] = next_color
			color[rb] = next_color + 1
			next_color += 2
		color[v] = color[ra]
		color[v + n_vertices] = color[rb]
	return color[:n_vertices]
(n, m) = list(map(int, input().split()))
mat = [[True] * t for t in range(n)]
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	if a < b:
		(a, b) = (b, a)
	mat[a - 1][b - 1] = False
edges = ((a, b) for a in range(n) for b in range(a) if mat[a][b])
colors = check_bipartiteness(n, edges)
if colors is None:
	print(-1)
	return
cnt = Counter(colors)
dp = np.zeros(n, dtype=bool)
dp[0] = True
for i in range(n):
	(a, b) = (cnt[i * 2], cnt[i * 2 + 1])
	if a == 0 and b == 0:
		break
	d = abs(a - b)
	if d == 0:
		continue
	ndp = np.zeros(n, dtype=bool)
	ndp[d:] = dp[:-d]
	ndp[:-d] |= dp[d:]
	ndp[:d] |= dp[d - 1::-1]
	dp = ndp
x = list(dp).index(True)
a = (n - x) // 2
b = n - a
print(a * (a - 1) // 2 + b * (b - 1) // 2)


from collections import deque
(N, M) = list(map(int, input().split()))
adj = [[1 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	adj[a][b] = 0
	adj[b][a] = 0
adj_inv = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
	for j in range(i + 1, N + 1):
		if adj[i][j] == 1:
			adj_inv[i].append(j)
			adj_inv[j].append(i)
seen = [0] * (N + 1)
num = []
for i in range(1, N + 1):
	if seen[i] == 0:
		plus = 0
		minus = 0
		que = deque()
		que.append(i)
		seen[i] = 1
		plus += 1
		while que:
			v = que.pop()
			u_list = adj_inv[v]
			for u in u_list:
				if seen[u] == 0:
					que.append(u)
					seen[u] = -seen[v]
					if seen[u] == 1:
						plus += 1
					else:
						minus += 1
				elif seen[u] == seen[v]:
					print(-1)
					return
		num.append((min(plus, minus), max(plus, minus)))
min_sum = 0
add = []
for i in range(len(num)):
	min_sum += num[i][0]
	add.append(num[i][1] - num[i][0])
dp = [[0 for _ in range(N // 2 + 1)] for _ in range(len(add) + 1)]
dp[0][min_sum] = 1
for i in range(len(add)):
	for j in range(min_sum, N // 2 + 1):
		if dp[i][j] == 1:
			if j + add[i] <= N // 2:
				dp[i + 1][j + add[i]] = 1
			dp[i + 1][j] = 1
dp_last = dp[-1]
for i in range(len(dp_last) - 1, -1, -1):
	if dp_last[i] == 1:
		N1 = i
		break
print(N1 * (N1 - 1) // 2 + (N - N1) * (N - N1 - 1) // 2)


import queue
(N, M) = list(map(int, input().split()))
G = [[1 for i in range(N)] for i in range(N)]
H = [[] for i in range(N)]
for i in range(N):
	G[i][i] -= 1
for i in range(M):
	(a, b) = list(map(int, input().split()))
	G[a - 1][b - 1] -= 1
	G[b - 1][a - 1] -= 1
for i in range(N):
	for j in range(N):
		if G[i][j] == 1:
			H[i].append(j)
A = [[[], []]]
k = 0
q = queue.Queue()
reached = [0 for i in range(N)]
dist = [-1 for i in range(N)]
for i in range(N):
	if reached[i] == 1:
		continue
	q.put(i)
	reached[i] = 1
	dist[i] = 0
	while not q.empty():
		r = q.get()
		A[k][dist[r]].append(r)
		for p in H[r]:
			if reached[p] == 0:
				q.put(p)
				dist[p] = (dist[r] + 1) % 2
				reached[p] = 1
	k += 1
	A.append([[], []])
for i in range(k):
	for j in range(2):
		for x in A[i][j]:
			for y in A[i][j]:
				if x == y:
					continue
				if G[x][y] == 1:
					print(-1)
					return
B = []
for i in range(k):
	B.append((len(A[i][0]), len(A[i][1])))
dp = [[0 for i in range(N + 1)] for i in range(k + 1)]
dp[0][0] = 1
for i in range(1, k + 1):
	for j in range(N + 1):
		if dp[i - 1][j] == 0:
			continue
		dp[i][j + B[i - 1][0]] = 1
		dp[i][j + B[i - 1][1]] = 1
delta = N
for i in range(N + 1):
	if dp[k][i] == 1:
		tmp = abs(N - 2 * i)
		if tmp < delta:
			delta = tmp
X = (N + delta) // 2
Y = (N - delta) // 2
print((X * (X - 1) + Y * (Y - 1)) // 2)


from collections import deque
(N, M) = map(int, input().split())
G0 = [set([i]) for i in range(N)]
A = set(range(N))
for i in range(M):
	(a, b) = map(int, input().split())
	G0[a - 1].add(b - 1)
	G0[b - 1].add(a - 1)
G = [A - g for g in G0]
b = 1
c = [-1] * N
for i in range(N):
	if c[i] != -1:
		continue
	p = 0
	s = 0
	que = deque([i])
	c[i] = 0
	while que:
		v = que.popleft()
		s += 1
		if c[v] == 0:
			p += 1
		for w in G[v]:
			if c[w] == -1:
				c[w] = c[v] ^ 1
				que.append(w)
			elif c[w] == c[v]:
				print(-1)
				exit(0)
	b = b << p | b << s - p
ans = 10 ** 18
for i in range(N + 1):
	if b >> i & 1:
		ans = min(ans, i * (i - 1) // 2 + (N - i) * (N - i - 1) // 2)
print(ans)


from collections import defaultdict, deque
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
edges = [list(range(N)) for i in range(N)]
for i in range(N):
	edges[i].remove(i)
for _ in range(M):
	(a, b) = map(int, input().split())
	edges[a - 1].remove(b - 1)
	edges[b - 1].remove(a - 1)
size = defaultdict(lambda : [0, 0])
color = [-1] * N

def set_color(root):
	que = deque([root])
	color[root] = 0
	size[root][0] += 1
	while que:
		v = que.pop()
		for nv in edges[v]:
			if color[nv] < 0:
				c = 1 - color[v]
				color[nv] = c
				size[root][c] += 1
				que.append(nv)
			elif color[nv] == color[v]:
				print(-1)
				sys.exit()
for i in range(N):
	if color[i] < 0:
		set_color(i)
S = set([0])
for (a, b) in size.values():
	S = set((s + b for s in S)) | set((s + a for s in S))
ans = min((x * (x - 1) // 2 + (N - x) * (N - x - 1) // 2 for x in S))
print(ans)


import sys
input = sys.stdin.readline

def is_bipartite(graph, s):
	n = len(graph)
	col = [-1] * n
	col[s] = 0
	stack = [s]
	used[s] = True
	while stack:
		v = stack.pop()
		for nxt_v in graph[v]:
			used[nxt_v] = True
			if col[nxt_v] == -1:
				col[nxt_v] = col[v] ^ 1
				stack.append(nxt_v)
			elif col[nxt_v] ^ col[v] == 0:
				return False
	return True

def color_bipartite(graph, s):
	n = len(graph)
	col = [-1] * n
	col[s] = 0
	stack = [s]
	while stack:
		v = stack.pop()
		for nxt_v in graph[v]:
			if col[nxt_v] == -1:
				col[nxt_v] = col[v] ^ 1
				stack.append(nxt_v)
	return col
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [set() for i in range(n)]
for (a, b) in info:
	a -= 1
	b -= 1
	graph[a].add(b)
	graph[b].add(a)
comp_graph = [[] for i in range(n)]
for a in range(n):
	for b in range(n):
		if b in graph[a] or a == b:
			continue
		comp_graph[a].append(b)
cnt0 = []
cnt1 = []
used = [False] * n
for i in range(n):
	if used[i]:
		continue
	used[i] = True
	if not is_bipartite(comp_graph, i):
		print(-1)
		return
	col = color_bipartite(comp_graph, i)
	cnt0.append(col.count(0))
	cnt1.append(col.count(1))
dp = [[False] * (n + 1) for i in range(len(cnt0) + 1)]
dp[0][0] = True
for i in range(len(cnt0)):
	wei0 = cnt0[i]
	wei1 = cnt1[i]
	for w in range(n + 1):
		if w + wei0 < n + 1:
			dp[i + 1][w + wei0] = dp[i][w] or dp[i + 1][w + wei0]
		if w + wei1 < n + 1:
			dp[i + 1][w + wei1] = dp[i][w] or dp[i + 1][w + wei1]
ans = 10 ** 18
for num in range(n + 1):
	if dp[-1][num]:
		c0 = num
		c1 = n - num
		res = c0 * (c0 - 1) // 2 + c1 * (c1 - 1) // 2
		ans = min(ans, res)
print(ans)


(N, M) = list(map(int, input().split()))
ROAD = [None] * M
for i in range(M):
	ROAD[i] = tuple(sorted(list(map(int, input().split()))))
import itertools
NOROAD = list(itertools.combinations(list(range(1, N + 1)), 2))
NOROAD = set(NOROAD) - set(ROAD)
Group = [[i, []] for i in range(N + 1)]

def find(x):
	while Group[x][0] != x:
		x = Group[x][0]
	return x
for i in NOROAD:
	(a, b) = i
	Group[a][1] += [b]
	Group[b][1] += [a]
	if find(a) != find(b):
		Group[find(a)][0] = min(find(a), find(b))
		Group[find(b)][0] = min(find(a), find(b))
		Group[a][0] = min(find(a), find(b))
		Group[b][0] = min(find(a), find(b))
GroupSORT = [[i, j[1]] for (i, j) in enumerate(Group)]
GroupSORT.sort(key=lambda x: len(x[1]))
NUMBERING = [[find(i), 'none'] for i in range(N + 1)]
CHECK = [0 for i in range(N + 1)]
for i in range(N):
	if CHECK[find(GroupSORT[i][0])] == 0:
		NUMBERING[GroupSORT[i][0]][1] = 0
		CHECK[find(GroupSORT[i][0])] = 1
CONDITION = 1
repeat_condition = 1
while repeat_condition == 1:
	repeat_condition = 0
	for i in range(1, N + 1):
		if NUMBERING[i][1] == 0:
			for j in Group[i][1]:
				if NUMBERING[j][1] == 0:
					CONDITION = 0
					break
				elif NUMBERING[j][1] == 'none':
					NUMBERING[j][1] = 1
					repeat_condition = 1
		if NUMBERING[i][1] == 1:
			for j in Group[i][1]:
				if NUMBERING[j][1] == 1:
					CONDITION = 0
					break
				elif NUMBERING[j][1] == 'none':
					NUMBERING[j][1] = 0
					repeat_condition = 1
import sys
if CONDITION == 0:
	print(-1)
	return
NUMBERS = set()
for i in range(1, len(NUMBERING)):
	NUMBERS = NUMBERS | {NUMBERING[i][0]}
count = []
for i in NUMBERS:
	count += [(i, NUMBERING.count([i, 0]), NUMBERING.count([i, 1]))]
DP = [set() for i in range(len(count))]
DP[0] = {count[0][1], count[0][2]}
for i in range(1, len(count)):
	for k in DP[i - 1]:
		DP[i] = DP[i] | {k + count[i][1], k + count[i][2]}
DIVIDE = list(DP[len(count) - 1])
for i in range(len(DIVIDE)):
	DIVIDE[i] = abs(DIVIDE[i] - N / 2)
x = int(min(DIVIDE) + N / 2)
print(x * (x - 1) // 2 + (N - x) * (N - x - 1) // 2)


def main(n, m, ab):
	g = [set((j for j in range(n) if j != i)) for i in range(n)]
	for (i, (a, b)) in enumerate(ab):
		(a, b) = (a - 1, b - 1)
		g[a].discard(b)
		g[b].discard(a)
	xy = []
	mi = set(range(n))
	seen = [-1] * n
	while mi:
		v = mi.pop()
		todo = [[v, -1]]
		seen[v] = 0
		xyi = [0, 0]
		xyi[0] += 1
		while todo:
			(v, p) = todo.pop()
			for nv in g[v]:
				if nv == p:
					continue
				if seen[nv] == -1:
					seen[nv] = (seen[v] + 1) % 2
					xyi[seen[nv]] += 1
					mi.discard(nv)
					todo.append([nv, v])
				elif seen[nv] != (seen[v] + 1) % 2:
					return -1
		xy.append(xyi)
	abl = [0] * (n + 1)
	abl[0] = 1
	for (x, y) in xy:
		for i in range(n, -1, -1):
			if abl[i] > 0:
				abl[i] = 0
				abl[i + x] = 1
				abl[i + y] = 1
	ans = m
	for (i, x) in enumerate(abl):
		if x == 0:
			continue
		j = n - i
		ans = min(ans, i * (i - 1) // 2 + j * (j - 1) // 2)
	return ans
(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
print(main(n, m, ab))


import sys
import math
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
connected = [set() for _ in range(N)]
for (a, b) in AB:
	a -= 1
	b -= 1
	connected[a].add(b)
	connected[b].add(a)
for i in range(N):
	connected[i].add(i)
whole_set = set(range(N))
unconnected = [whole_set - connected[i] for i in range(N)]
assign = [-1] * N
ass_q = []
g = 0
for i in range(N):
	if len(unconnected[i]) != 0:
		assign[i] = g
		for j in unconnected[i]:
			assign[j] = (assign[i] + 1) % 2 + g
			ass_q.append(j)
		break
while len(ass_q) > 0:
	i = ass_q.pop()
	for j in unconnected[i]:
		if assign[j] == -1:
			assign[j] = (assign[i] + 1) % 2 + g
			ass_q.append(j)
		elif assign[j] == assign[i]:
			print(-1)
			return
	if len(ass_q) == 0:
		g += 2
		for i in range(N):
			if len(unconnected[i]) > 0 and assign[i] == -1:
				assign[i] = g
				for j in unconnected[i]:
					assign[j] = (assign[i] + 1) % 2 + g
					ass_q.append(j)
				break
groups = [(assign.count(g_), assign.count(g_ + 1)) for g_ in range(0, g, 2)]
ans = math.inf
not_assign = assign.count(-1)
for b in range(pow(2, len(groups))):
	(taka, hashi) = (0, 0)
	for i in range(len(groups)):
		taka += groups[i][b >> i & 1]
		hashi += groups[i][~b >> i & 1]
	for _ in range(not_assign):
		if taka < hashi:
			taka += 1
		else:
			hashi += 1
	ans = min(ans, taka * (taka - 1) // 2 + hashi * (hashi - 1) // 2)
print(ans)


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return list(map(int, input().split()))

def LI():
	return list(map(int, input().split()))
mod = 10 ** 9 + 7
from collections import defaultdict

class UnionFind:

	def __init__(self, N: int):
		self.N = N
		self.root = [-1] * N
		self.rank = [0] * N

	def __repr__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

	def find(self, x: int):
		if self.root[x] < 0:
			return x
		else:
			while self.root[x] >= 0:
				x = self.root[x]
			return x

	def union(self, x: int, y: int):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def same(self, x: int, y: int):
		return self.find(x) == self.find(y)

	def count(self, x):
		return -self.root[self.find(x)]

	def members(self, x):
		_root = self.find(x)
		return [i for i in range(self.N) if self.find == _root]

	def roots(self):
		return [i for (i, x) in enumerate(self.root) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		dd = defaultdict(list)
		for i in range(N):
			root = self.find(i)
			dd[root].append(i)
		return dd

class Scc_graph:

	def __init__(self, N):
		self.N = N
		self.edges = []

	def csr(self):
		start = [0] * (self.N + 1)
		elist = [0] * len(self.edges)
		for (v, w) in self.edges:
			start[v + 1] += 1
		for i in range(1, self.N + 1):
			start[i] += start[i - 1]
		counter = start.copy()
		for (v, w) in self.edges:
			elist[counter[v]] = w
			counter[v] += 1
		self.start = start
		self.elist = elist

	def add_edge(self, v, w):
		self.edges.append((v, w))

	def scc_ids(self):
		self.csr()
		N = self.N
		now_ord = group_num = 0
		visited = []
		low = [0] * N
		order = [-1] * N
		ids = [0] * N
		parent = [-1] * N
		stack = []
		for i in range(N):
			if order[i] == -1:
				stack.append(~i)
				stack.append(i)
				while stack:
					v = stack.pop()
					if v >= 0:
						if order[v] == -1:
							low[v] = order[v] = now_ord
							now_ord += 1
							visited.append(v)
							for i in range(self.start[v], self.start[v + 1]):
								to = self.elist[i]
								if order[to] == -1:
									stack.append(~to)
									stack.append(to)
									parent[to] = v
								else:
									low[v] = min(low[v], order[to])
					else:
						v = ~v
						if low[v] == order[v]:
							while True:
								u = visited.pop()
								order[u] = N
								ids[u] = group_num
								if u == v:
									break
							group_num += 1
						if parent[v] != -1:
							low[parent[v]] = min(low[parent[v]], low[v])
		for (i, x) in enumerate(ids):
			ids[i] = group_num - 1 - x
		return (group_num, ids)

	def scc(self):
		(group_num, ids) = self.scc_ids()
		groups = [[] for _ in range(group_num)]
		for (i, x) in enumerate(ids):
			groups[x].append(i)
		return groups

class Two_sat:

	def __init__(self, N):
		self.N = N
		self.answer = []
		self.scc = Scc_graph(2 * N)

	def add_clause(self, i, f, j, g):
		self.scc.add_edge(2 * i + (f == 0), 2 * j + (g == 1))
		self.scc.add_edge(2 * j + (g == 0), 2 * i + (f == 1))

	def satisfiable(self):
		(_, ids) = self.scc.scc_ids()
		self.answer.clear()
		for i in range(self.N):
			if ids[2 * i] == ids[2 * i + 1]:
				self.answer.clear()
				return False
			self.answer.append(ids[2 * i] < ids[2 * i + 1])
		return True
(N, M) = MI()
inf = N + 5
d = [[inf] * N for _ in range(N)]
for i in range(N):
	d[i][i] = 0
for _ in range(M):
	(a, b) = MI()
	a -= 1
	b -= 1
	d[a][b] = 1
	d[b][a] = 1

def calc(x):
	return x * (x - 1) // 2
uf = UnionFind(N)
for i in range(N):
	for j in range(i + 1, N):
		if d[i][j] > 1:
			uf.union(i, j)
roots = uf.roots()
Nr = len(roots)
G = [[] for _ in range(Nr)]
from collections import defaultdict
dd = defaultdict(int)
cnt = 0
for v in roots:
	dd[v] = cnt
	cnt += 1
for i in range(N):
	r = uf.find(i)
	rnum = dd[r]
	G[rnum].append(i)
allOK = 0
D = []
S1 = 0
S2 = 0
for g in G:
	Ng = len(g)
	if Ng == 1:
		allOK += 1
		continue
	g.sort()
	ts = Two_sat(Ng)
	for i in range(Ng):
		for j in range(i + 1, Ng):
			a = g[i]
			b = g[j]
			if d[a][b] != 1:
				ts.add_clause(i, 0, j, 0)
				ts.add_clause(i, 1, j, 1)
	if not ts.satisfiable():
		print(-1)
		return
	a = sum(ts.answer)
	b = Ng - a
	S1 += min(a, b)
	S2 += min(a, b)
	if a != b:
		D.append(abs(a - b))
Nd = len(D)
geta = 1000
dp = [[0] * (geta * 2 + 1) for _ in range(Nd + 1)]
dp[0][geta] = 1
for (i, num) in enumerate(D):
	for j in range(geta * 2 + 1):
		if dp[i][j]:
			dp[i + 1][j - num] = 1
			dp[i + 1][j + num] = 1
diff = geta
for j in range(geta + 1):
	if dp[-1][j]:
		diff = min(diff, abs(j - geta))
Sd = sum(D)
s11 = (Sd - diff) // 2
s12 = Sd - s11
S1 += s11
S2 += s12
ds = S2 - S1
if ds > allOK:
	ans = calc(S2) + calc(S1 + allOK)
else:
	aa = N // 2
	bb = N - aa
	ans = calc(aa) + calc(bb)
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
G = [[1] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a][b] = G[b][a] = 0
colors = [-1 for i in range(n)]
possible = True
ni = []

def dfs(x, y):
	colors[x] = y
	k[y] += 1
	for l in range(n):
		if l == x or G[x][l] == 0:
			continue
		if colors[l] == -1:
			dfs(l, 1 - y)
		elif colors[l] != 1 - y:
			nonlocal possible
			possible = False
for i in range(n):
	k = [0, 0]
	if colors[i] != -1:
		continue
	dfs(i, 0)
	ni.append([k[0], k[1]])
if possible == False:
	print(-1)
	return
dp = [0] * 701
dp[0] = 1
for i in ni:
	for j in range(700, -1, -1):
		if dp[j]:
			dp[j] = 0
			dp[j + i[0]] = 1
			dp[j + i[1]] = 1
ans = float('inf')
for i in range(0, 701):
	if dp[i]:
		tmp = (n - i) * (n - i - 1) // 2 + i * (i - 1) // 2
		ans = min(tmp, ans)
print(ans)


class Graph:

	def __init__(self, nvert, edges):
		self.adj = [[False] * nvert for i in range(nvert)]
		for e in edges:
			(u, v) = e
			self.adj[u][v] = True
			self.adj[v][u] = True

	def __str__(self):
		return str(self.adj)

	def nvertices(self):
		return len(self.adj)

	def complement(self):
		nv = len(self.adj)
		g = Graph(nv, [])
		for u in range(nv):
			for v in range(nv):
				if u == v:
					continue
				g.adj[u][v] = not self.adj[u][v]
				g.adj[v][u] = not self.adj[v][u]
		return g

	def connectedcomps(self):
		self.visited = [False] * self.nvertices()
		ccs = []
		for v in range(self.nvertices()):
			if not self.visited[v]:
				vs = []
				self.__connectedcomp(v, vs)
				cc = self.inducedsubgraph(vs)
				ccs.append(cc)
		self.visited = None
		return ccs

	def __connectedcomp(self, v, vs):
		if self.visited[v]:
			return
		self.visited[v] = True
		vs.append(v)
		for u in range(self.nvertices()):
			if self.adj[v][u]:
				self.__connectedcomp(u, vs)

	def inducedsubgraph(self, vs):
		n = len(vs)
		m = {}
		for i in range(n):
			m[vs[i]] = i
		sg = Graph(n, [])
		for v in vs:
			for u in range(self.nvertices()):
				if self.adj[v][u]:
					sg.adj[m[v]][m[u]] = True
					sg.adj[m[u]][m[v]] = True
		return sg

	def isbipartite(self):
		self.color = [None] * self.nvertices()
		self.color[0] = 0
		if not self.__isbipartite(0):
			return False
		m = sum((1 for c in self.color if c == 0))
		n = sum((1 for c in self.color if c == 1))
		assert m + n == self.nvertices()
		return (max(m, n), min(m, n))

	def __isbipartite(self, v):
		for u in range(self.nvertices()):
			if self.adj[v][u]:
				if self.color[u] == None:
					self.color[u] = 1 - self.color[v]
					if not self.__isbipartite(u):
						return False
				elif self.color[u] != 1 - self.color[v]:
					return False
		return True
(N, M) = [int(w) for w in input().split()]
edges = []
for i in range(M):
	(a, b) = [int(w) for w in input().split()]
	edges.append((a - 1, b - 1))
g = Graph(N, edges).complement()
ccs = g.connectedcomps()
bs = [cc.isbipartite() for cc in ccs]
if not all(bs):
	print(-1)
	exit()
diffs = [t[0] - t[1] for t in bs]
sums = {0}
for d in diffs:
	newsums = set()
	for s in sums:
		newsums.add(s + d)
	sums.update(newsums)
halfdiff = sum(diffs) / 2
nearlyhalfdiff = min(((abs(s - halfdiff), s) for s in sums))[1]
diff = abs(sum(diffs) - 2 * nearlyhalfdiff)
x = (N - diff) // 2
y = N - x
x = x * (x - 1) // 2
y = y * (y - 1) // 2
print(x + y)


import sys
(N, M) = map(int, input().split())
AB = []
olis = [[1] * N for i in range(N)]
for i in range(N):
	olis[i][i] = 0
for i in range(M):
	(A, B) = map(int, input().split())
	A -= 1
	B -= 1
	olis[A][B] = 0
	olis[B][A] = 0
non_visit = [True] * N
state = [None] * N
dif = []
ns = [0, 0]

def dfs(p, nst):
	if non_visit[p]:
		non_visit[p] = False
		state[p] = nst
		ns[nst] += 1
		for j in range(N):
			if p != j and olis[p][j] == 1:
				dfs(j, nst ^ 1)
	elif nst != state[p]:
		print(-1)
		sys.exit()
	return
for i in range(N):
	ns = [0, 0]
	if non_visit[i]:
		dfs(i, 0)
		dif.append(abs(ns[0] - ns[1]))
dp = [False] * 1500
dp[0] = True
for i in dif:
	ndp = [False] * 1500
	for j in range(1500):
		if dp[j]:
			ndp[(j - i) % 1500] = True
			ndp[(j + i) % 1500] = True
	dp = ndp
for i in range(N):
	if dp[i] or dp[-1 * i]:
		for j in range(N):
			if abs(N - j - j) == i:
				x = j
				y = N - j
				print(x * (x - 1) // 2 + y * (y - 1) // 2)
				sys.exit()


import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, m) = list(map(int, readline().split()))
g = [[1] * n for _ in range(n)]
for i in range(n):
	g[i][i] = 0
for _ in range(m):
	(a, b) = list(map(int, readline().split()))
	g[a - 1][b - 1] = g[b - 1][a - 1] = 0
used = [-1] * n
dp = 1
ok = 1
for i in range(n):
	if used[i] == -1:
		used[i] = 0
		st = [i]
		a = b = 0
		while st:
			v = st.pop()
			c = used[v]
			if c:
				a += 1
			else:
				b += 1
			for k in range(n):
				if g[v][k] == 1:
					if used[k] == -1:
						used[k] = 1 - c
						st.append(k)
					elif used[k] == c:
						ok = 0
						break
		dp = dp << a | dp << b
		if not ok:
			dp = 0
			break
ans = -1
for i in range(n // 2 + 1):
	if dp >> i & 1:
		ans = i * (i - 1) // 2 + (n - i) * (n - i - 1) // 2
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
es = [tuple(map(lambda x: int(x) - 1, input().split())) for i in range(M)]
gr = [[0 for j in range(N)] for i in range(N)]
for (a, b) in es:
	gr[a][b] = gr[b][a] = 1
compgr = [[] for i in range(N)]
for i in range(N - 1):
	for j in range(i + 1, N):
		if gr[i][j]:
			continue
		compgr[i].append(j)
		compgr[j].append(i)
colors = [0] * N

def dfs(v, color):
	colors[v] = color
	(b, w) = (1, 0) if color == 1 else (0, 1)
	for to in compgr[v]:
		if colors[to] == color:
			print(-1)
			exit()
		elif colors[to] == 0:
			(db, dw) = dfs(to, -color)
			b += db
			w += dw
	return [b, w]
dp = set([0])
for i in range(N):
	if colors[i] != 0:
		continue
	(b, w) = dfs(i, 1)
	dp2 = set()
	for n in dp:
		dp2.add(n + b)
		dp2.add(n + w)
	dp = dp2
ans = N * N
for a in dp:
	b = N - a
	tmp = a * (a - 1) // 2 + b * (b - 1) // 2
	ans = min(ans, tmp)
print(ans)


from collections import deque
import sys
from operator import itemgetter
(N, M) = map(int, input().split())
table = [[1] * N for i in range(N)]
for i in range(N):
	table[i][i] = 0
for i in range(M):
	(a, b) = map(int, input().split())
	table[a - 1][b - 1] = 0
	table[b - 1][a - 1] = 0
visit = [False] * N
color = [-1] * N

def f(i):
	q = deque()
	q.append(i)
	color[i] = 0
	visit[i] = True
	r = [0, 0]
	r[0] += 1
	while q:
		x = q.popleft()
		for j in range(N):
			if table[x][j] == 0:
				continue
			if visit[j]:
				if color[x] == color[j]:
					print(-1)
					sys.exit()
				continue
			q.append(j)
			color[j] = (color[x] + 1) % 2
			r[color[j]] += 1
			visit[j] = True
	return r
ans = []
for i in range(N):
	if not visit[i]:
		ans.append(f(i))
r = sorted(ans, reverse=True)
for i in range(1, len(ans)):
	if r[0][0] > r[0][1]:
		r[0][0] += min(r[i][0], r[i][1])
		r[0][1] += max(r[i][0], r[i][1])
	else:
		r[0][0] += max(r[i][0], r[i][1])
		r[0][1] += min(r[i][0], r[i][1])

def dou(k):
	return k * (k - 1) // 2
print(dou(r[0][0]) + dou(r[0][1]))


import sys
(N, M) = list(map(int, input().split()))
I = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	I[a][b] = 1
	I[b][a] = 1
for a in range(N):
	I[a][a] = 1
R = []
B = []
vis = set()

def dfs(s, c):
	adj = I[s]
	tmp = True
	r_ct = 0
	b_ct = 0
	clr[s] = c
	for p in range(N):
		if adj[p] == 1:
			continue
		if p in vis:
			if clr[p] != 1 - c:
				return False
			continue
		else:
			vis.add(p)
			if not dfs(p, 1 - c):
				return False
	return True
vis = set()
ans = 0
used_edge = 0
for s in range(N):
	if s in vis:
		continue
	R.append(0)
	B.append(0)
	clr = {}
	vis.add(s)
	if not dfs(s, 0):
		print(-1)
		return
	for p in clr:
		if clr[p] == 0:
			R[-1] += 1
		else:
			B[-1] += 1
	for p in clr:
		for q in clr:
			if p != q and I[p][q] == 1:
				used_edge += 1
				if clr[p] == clr[q]:
					ans += 1
DP = 1
for i in range(len(R)):
	DP = DP << R[i] | DP << B[i]
i = 0
ex = []
while DP > 0:
	if DP % 2 == 1:
		ex.append(i)
	i += 1
	DP >>= 1
ex.sort(key=lambda x: abs(2 * x - N))
tmp = ex[0] * (N - ex[0])
for i in range(len(R)):
	tmp -= R[i] * B[i]
ans //= 2
ans += (2 * M - used_edge) // 2 - tmp
print(ans)