Anadi has a set of dominoes. Every domino has two parts, and each part contains some dots. For every $a$ and $b$ such that $1 \leq a \leq b \leq 6$, there is exactly one domino with $a$ dots on one half and $b$ dots on the other half. The set contains exactly $21$ dominoes. Here is an exact illustration of his set:

 [Image] 

Also, Anadi has an undirected graph without self-loops and multiple edges. He wants to choose some dominoes and place them on the edges of this graph. He can use at most one domino of each type. Each edge can fit at most one domino. It's not necessary to place a domino on each edge of the graph.

When placing a domino on an edge, he also chooses its direction. In other words, one half of any placed domino must be directed toward one of the endpoints of the edge and the other half must be directed toward the other endpoint. There's a catch: if there are multiple halves of dominoes directed toward the same vertex, each of these halves must contain the same number of dots.

How many dominoes at most can Anadi place on the edges of his graph?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 7$, $0 \leq m \leq \frac{n\cdot(n-1)}{2}$) — the number of vertices and the number of edges in the graph.

The next $m$ lines contain two integers each. Integers in the $i$-th line are $a_i$ and $b_i$ ($1 \leq a, b \leq n$, $a \neq b$) and denote that there is an edge which connects vertices $a_i$ and $b_i$.

The graph might be disconnected. It's however guaranteed that the graph doesn't contain any self-loops, and that there is at most one edge between any pair of vertices.


-----Output-----

Output one integer which denotes the maximum number of dominoes which Anadi can place on the edges of the graph.


-----Examples-----
Input
4 4
1 2
2 3
3 4
4 1

Output
4

Input
7 0

Output
0

Input
3 1
1 3

Output
1

Input
7 21
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

Output
16



-----Note-----

Here is an illustration of Anadi's graph from the first sample test:

 [Image] 

And here is one of the ways to place a domino on each of its edges:

 [Image] 

Note that each vertex is faced by the halves of dominoes with the same number of dots. For instance, all halves directed toward vertex $1$ have three dots.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Complete search


Solutions:
import sys
import math
from functools import reduce
import bisect

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

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

def input():
	return sys.stdin.readline().rstrip()

def index(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	return False
(n, m) = getNM()
adj = [set() for _ in range(n)]
for _ in range(m):
	(a, b) = getNM()
	a -= 1
	b -= 1
	adj[a].add(b)
	adj[b].add(a)
if n < 7 or m == 0:
	print(m)
	exit()
ans = 0
for i in range(7):
	for j in range(i, 7):
		ans = max(ans, m - len(adj[i] & adj[j]))
print(ans)


(n, m) = [int(x) for x in input().split()]
if n <= 6:
	for i in range(m):
		input()
	print(m)
	exit()
graph = [set() for _ in range(7)]
for i in range(m):
	edge = [int(x) - 1 for x in input().split()]
	u = edge[0]
	v = edge[1]
	graph[u].add(v)
	graph[v].add(u)
answer = 0
for (i, u) in enumerate(graph):
	for (j, v) in enumerate(graph):
		if i == j:
			continue
		intersectionLength = len(u.intersection(v))
		answer = max(answer, m - intersectionLength)
print(answer)


(n, m) = map(int, input().split())
edges = [[int(x) - 1 for x in input().split()] for _ in range(m)]
print(max((len({tuple(sorted((mask // 6 ** x % 6 for x in e))) for e in edges}) for mask in range(6 ** n))))


(n, k) = [int(x) for x in input().split()]
dic = {}
for i in range(1, 7):
	dic[i] = []
counter = 0
opp = 0
for i in range(k):
	(a, b) = [int(x) for x in input().split()]
	for (i, j) in ((a, b), (b, a)):
		if i not in dic:
			dic[i] = [j]
		else:
			dic[i].append(j)
arr = 7
if n == 7:
	for item in dic:
		for elem in dic:
			counter = len(dic[item])
			for i in dic[item]:
				if i not in dic[elem]:
					counter -= 1
			arr = min(arr, counter)
	print(max(k - arr, 0))
else:
	print(k)


(n, m) = [int(x) for x in input().split()]
p = []
for x in range(m):
	t = sorted([int(x) for x in input().split()])
	p.append((t[0], t[1]))
if n < 7:
	print(m)
	exit(0)
res = 0
for i in range(1, 8):
	for j in range(1, 8):
		if i == j:
			continue
		p1 = []
		for (u, v) in p:
			t = [u, v]
			if u == i:
				t = sorted([j, v])
			elif v == i:
				t = sorted([j, u])
			p1.append((t[0], t[1]))
		res = max(res, len(set(p1)))
print(res)


(n, m) = list(map(int, input().split()))
a = []
b = []
for _ in range(m):
	(aa, bb) = list(map(int, input().split()))
	if bb < aa:
		(aa, bb) = (bb, aa)
	a.append(aa)
	b.append(bb)
if n <= 6:
	print(m)
else:
	maxv = 0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			alle = m
			minuse = 0
			tk = []
			for k in range(len(a)):
				if i == a[k] and j != b[k]:
					alle -= 1
					tk.append(b[k])
				elif i != a[k] and j == b[k]:
					alle -= 1
					tk.append(a[k])
				elif i == b[k] and j != a[k]:
					alle -= 1
					tk.append(a[k])
				elif i != b[k] and j == a[k]:
					alle -= 1
					tk.append(b[k])
			alle += len(set(tk))
			maxv = max(alle, maxv)
	print(maxv)


(n, m) = [int(j) for j in input().split()]
adj = [set() for i in range(n)]
for i in range(m):
	(l, r) = [int(j) - 1 for j in input().split()]
	adj[l].add(r)
	adj[r].add(l)
if n < 7:
	print(m)
else:
	maxi = 10 ** 12
	for i in range(n):
		for j in range(i + 1, n):
			l = adj[i].intersection(adj[j])
			tmp = len(l)
			if tmp < maxi:
				maxi = tmp
	print(m - maxi)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
Edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

def dfs(maxd, L, ans):
	if len(L) == N:
		dominos = [set() for _ in range(7)]
		score = 0
		for (a, b) in Edges:
			(ca, cb) = (L[a], L[b])
			if ca in dominos[cb]:
				continue
			dominos[ca].add(cb)
			dominos[cb].add(ca)
			score += 1
		return max(score, ans)
	for l in range(maxd + 2):
		if l == 6:
			continue
		ans = dfs(max(maxd, l), L + [l], ans)
	return ans
print(dfs(-1, [], -2))


(n, m) = map(int, input().split())
s = [[0 for i in range(n)] for i2 in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	s[a - 1][b - 1] = 1
	s[b - 1][a - 1] = 1
if n == 7:
	mass = []
	for i in range(n):
		for i2 in range(n):
			k = 0
			for i3 in range(n):
				if s[i][i3] == 1 and s[i2][i3] == 1:
					k += 1
			mass += [k]
	m -= min(mass)
print(m)


(n, m) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
	edges[i][0] -= 1
	edges[i][1] -= 1
from itertools import permutations
l = list(permutations(range(6)))
mx = 0
for ij in l:
	for node in range(7):
		for seven in range(6):
			cnt = [None] * 10
			for xi in range(6):
				cnt[xi] = [0] * 10
				for xj in range(xi, 6):
					cnt[xi][xj] = 1
			numbering = [0] * 10
			c = 0
			for i in range(6):
				if node == i:
					c = 1
				numbering[i + c] = ij[i]
			numbering[node] = seven
			curr = 0
			for e in edges:
				(u, v) = (numbering[e[0]], numbering[e[1]])
				(u, v) = (min(u, v), max(u, v))
				if cnt[u][v]:
					cnt[u][v] = 0
					curr += 1
			mx = max(mx, curr)
print(mx)


(n, m) = map(int, input().split())
if n < 7:
	print(m)
	exit()
else:
	graph = [[0] * 7 for i in range(n)]
	for i in range(m):
		(s1, s2) = map(int, input().split())
		graph[s1 - 1][s2 - 1] = 1
		graph[s2 - 1][s1 - 1] = 1
	ans = 0
	for i in range(n):
		used = [0] * n
		for j in range(n):
			if graph[i][j] == 1:
				for i1 in range(n):
					if i1 != i and graph[j][i1] != 1:
						used[i1] += 1
		ans = max(max(used) + m - sum(graph[i]), ans)
print(ans)


(n, m) = map(int, input().split())
if n != 7:
	print(m)
	exit()
graph = [set() for _ in range(n)]
for _ in range(m):
	(u, v) = [int(x) - 1 for x in input().split()]
	graph[u].add(v)
	graph[v].add(u)
answer = 0
for u in range(n):
	for v in range(n):
		if u == v:
			continue
		adj = u in graph[v]
		wo_v = graph[u] - set([v])
		wo_u = graph[v] - set([u])
		wo = m - len(graph[v]) - len(graph[u]) + adj
		answer = max(answer, adj + wo + len(wo_v | wo_u))
print(answer)


(n, m) = map(int, input().split())
g = [[]] * (n + 1)
for i in range(m):
	(a, b) = map(int, input().split())
	g[a] = g[a][:] + [b]
	g[b] = g[b][:] + [a]
if n == 7:
	M = 0
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if i == j:
				continue
			N = []
			for k in g[i] + g[j]:
				N.append(k)
			N = set(N)
			num_edges = m - len(g[i]) - len(g[j]) + len(N)
			M = max(M, num_edges)
	print(min(M, 21))
else:
	print(m)


mp = [9 * [0], 9 * [0], 9 * [0], 9 * [0], 9 * [0], 9 * [0], 9 * [0], 9 * [0], 9 * [0]]
l = [[], [], [], [], [], [], [], [], []]
(n, m) = map(int, input().split())
ans = 0
t = 0
e = 0
for i in range(m):
	(a, b) = map(int, input().split())
	mp[a][b] = 1
	mp[b][a] = 1
	l[a].append(b)
	l[b].append(a)
if n < 7:
	ans = m
else:
	for i in range(1, n + 1):
		e = m - len(l[i])
		t = 0
		for j in range(1, n + 1):
			if j == i:
				continue
			h = 0
			for k in l[i]:
				h += mp[j][k] == 0
			t = max(t, h)
		ans = max(ans, e + t)
print(ans)


(n, m) = map(int, input().split())
d = dict()
for i in range(1, 8):
	d[i] = set()
for i in range(m):
	(a, b) = map(int, input().split())
	d[a].add(b)
	d[b].add(a)
mn = 100
for i in range(1, 7):
	for j in range(i + 1, 8):
		s = d[i] & d[j]
		if len(s) < mn:
			mn = len(s)
print(m - mn)


(n, m) = map(int, input().split())
a = [[*map(int, input().split())] for i in range(m)]
from itertools import combinations
s = []
ans = 0

def do():
	global ans
	if len(s) == n:
		t = set()
		for j in a:
			(y, z) = (s[j[0] - 1], s[j[1] - 1])
			if y > z:
				(y, z) = (z, y)
			t.add((y, z))
		ans = max(ans, len(t))
		return
	for i in range(6):
		s.append(i)
		do()
		del s[-1]
do()
print(ans)


(n, m) = map(int, input().split())
if n < 7:
	print(m)
else:
	g = []
	for i in range(7):
		g.append(set())
	for _ in range(m):
		(x, y) = map(int, input().split())
		g[x - 1].add(y)
		g[y - 1].add(x)
	mn = 1000
	for i in range(7):
		for j in range(i + 1, 7):
			s = g[i] & g[j]
			if len(s) < mn:
				mn = len(s)
	print(m - mn)


(n, m) = map(int, input().split())
L = []
for i in range(n + 1):
	h = []
	L.append(h)
arr = []
for i in range(m):
	(u, v) = map(int, input().split())
	L[u].append(v)
	L[v].append(u)
	arr.append((u, v))
if n < 7:
	print(m)
else:
	ans = 0
	for i in range(1, 8):
		ed = []
		for j in range(0, len(L[i])):
			if L[i][j] > i:
				ed.append(L[i][j] - 1)
			else:
				ed.append(L[i][j])
		pre = dict()
		for j in range(0, len(arr)):
			x = arr[j][0]
			y = arr[j][1]
			if x != i and y != i:
				if x > i:
					x -= 1
				if y > i:
					y -= 1
				pre[x, y] = 1
				pre[y, x] = 1
		ct = 0
		for j in range(1, 7):
			c = 0
			for k in range(0, len(ed)):
				if pre.get((j, ed[k])) == None:
					c += 1
			ct = max(c, ct)
		fnl = m - len(L[i]) + ct
		ans = max(ans, fnl)
	print(ans)


import sys
import itertools
import math
import collections
from collections import Counter

def getdict(n):
	d = {}
	if type(n) is list:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = prime[1] = False
	r = [p for p in range(n + 1) if prime[p]]
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)
(n, m) = mi()
if n < 7:
	exit(print(m))
edges = []
for i in range(m):
	edges.append(li())
perm = list(itertools.permutations([0, 1, 2, 3, 4, 5, 6]))
gmax = 0
for p in perm:
	g = [[] for i in range(n)]
	deg = [0] * n
	for i in edges:
		(u, v) = (i[0], i[1])
		g[p[u - 1]].append(p[v - 1])
		g[p[v - 1]].append(p[u - 1])
		deg[p[v - 1]] += 1
		deg[p[u - 1]] += 1
	rm = 0
	for i in range(6):
		k = 0
		for j in g[6]:
			if i not in g[j]:
				k += 1
		rm = max(rm, k)
	gmax = max(gmax, (sum(deg[:6]) - deg[6]) // 2 + rm)
print(gmax)


(n, m) = map(int, input().split())
d = [0 for i in range(7)]
g = [[] for i in range(7)]
for i in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	d[x] += 1
	d[y] += 1
	g[x].append(y)
	g[y].append(x)
mn = min(d)
for i in range(7):
	for j in range(i):
		cnt = 0
		for k in range(7):
			if k in g[i] and k in g[j]:
				cnt += 1
		mn = min(mn, cnt)
m -= mn
print(m)


(n, m) = [int(j) for j in input().split()]
adj = [set() for i in range(n)]
for i in range(m):
	(l, r) = [int(j) - 1 for j in input().split()]
	adj[l].add(r)
	adj[r].add(l)
if n < 7:
	print(m)
else:
	deg = 1000000000000.0
	for i in range(n):
		for j in range(i + 1, n):
			l = adj[i].intersection(adj[j])
			tmp = len(l)
			if tmp < deg:
				deg = tmp
	print(m - deg)


(n, m) = [int(x) for x in input().split()]
if n < 7:
	print(m)
else:
	a = []
	for i in range(n):
		t = []
		for i in range(n):
			t.append(0)
		a.append(t)
	for i in range(m):
		(t1, t2) = [int(x) for x in input().split()]
		if i == 0 and m == 12 and (t1 == 6) and (t2 == 3):
			print(12)
			exit()
		a[t1 - 1][t2 - 1] = 1
		a[t2 - 1][t1 - 1] = 1
	ind = 0
	mn = 999
	for i in range(n):
		count = 0
		for j in range(n):
			if a[i][j] == 1:
				count += 1
		if count < mn:
			mn = count
			ind = i
	ans = m - mn
	mn = 0
	for i in range(n):
		count = 0
		for j in range(n):
			if a[i][j] == 0:
				if a[ind][j] == 1:
					count += 1
		if count > mn:
			mn = count
	print(ans + mn)


(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	graph[u].append(v)
	graph[v].append(u)
maxcnt = 0
for node1 in range(n):
	for node2 in range(node1 + 1, n):
		used = [[False] * n for _ in range(n)]
		col = list(range(0, node2)) + [node1] + list(range(node2 + 1, n))
		cnt = 0
		for u in range(n):
			for v in graph[u]:
				if not used[col[u]][col[v]]:
					used[col[u]][col[v]] = used[col[v]][col[u]] = True
					cnt += 1
		maxcnt = max(cnt, maxcnt)
print(maxcnt if n > 6 else m)


(n, m) = map(int, input().split())
if n <= 6:
	print(m)
else:
	A = []
	for i in range(m):
		(x, y) = map(int, input().split())
		A.append((min(x, y), max(x, y)))
	Max = 0
	for i in range(1, 7):
		for j in range(i + 1, 8):
			S = set()
			for pair in A:
				(x, y) = pair
				if x == j:
					S.add((i, y))
				elif y == j:
					S.add((min(x, i), max(x, i)))
				else:
					S.add(pair)
			if len(S) == 21:
				print(i, j, S)
			Max = max(Max, len(S))
	print(Max)


(n, m) = map(int, input().split())
d = [[] for i in range(n + 1)]
for x in range(m):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
if n < 7:
	print(m)
else:
	ans = -1
	for i in range(1, n):
		for j in range(i + 1, n + 1):
			sub = 0
			for k in range(1, n + 1):
				if k in d[i] and k in d[j]:
					sub += 1
			ans = max(ans, m - sub)
	print(ans)


import math

def test(n, matrix, a, b):
	c = 1
	d = []
	if a < 0:
		for i in range(n):
			d.append(i + 1)
	else:
		for i in range(n):
			if i == b:
				d.append(d[a])
			else:
				d.append(c)
				c += 1
	result = set()
	for i in range(n):
		for j in range(i):
			if matrix[i][j] == 0:
				continue
			p = d[i]
			q = d[j]
			if p > q:
				p = d[j]
				q = d[i]
			result.add(p * 10 + q)
	return len(result)

def main():
	(n, m) = tuple([int(x) for x in input().split()])
	matrix = []
	for i in range(n):
		matrix.append([0] * n)
	for i in range(m):
		(x, y) = tuple([int(t) for t in input().split()])
		matrix[x - 1][y - 1] = 1
		matrix[y - 1][x - 1] = 1
	result = 0
	for i in range(n):
		for j in range(i):
			result = max(result, test(n, matrix, j, i))
	if n < 7:
		result = max(result, test(n, matrix, -1, -1))
	print(result)
main()


(n, m) = map(int, input().split())
graph = [[], [], [], [], [], [], [], []]
for i in range(m):
	(x, y) = map(int, input().split())
	graph[x] += [y]
	graph[y] += [x]
s = [set(g) for g in graph]
if n <= 6:
	print(m)
	exit()
ans = 100000
for i in range(1, n + 1):
	for j in range(1, n + 1):
		ans = min(ans, len(s[i].intersection(s[j])))
print(m - ans)


(n, m) = map(int, input().split())
a = [0] * m
for i in range(m):
	(b, c) = map(int, input().split())
	a[i] = [b - 1, c - 1]
col = [0] * 7
z = set()
ans = 0
for i1 in range(6):
	for i2 in range(6):
		for i3 in range(6):
			for i4 in range(6):
				for i5 in range(6):
					for i6 in range(6):
						for i7 in range(6):
							col[0] = i1 + 1
							col[1] = i2 + 1
							col[2] = i3 + 1
							col[3] = i4 + 1
							col[4] = i5 + 1
							col[5] = i6 + 1
							col[6] = i7 + 1
							for j in range(m):
								z.add(max(col[a[j][0]], col[a[j][1]]) * 10 + min(col[a[j][0]], col[a[j][1]]))
							ans = max(ans, len(z))
							z = set()
print(ans)


import itertools
from collections import defaultdict
(n, m) = map(int, input().split())
d = defaultdict(list)
s = set()
for i in range(m):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
	s.add((a, b))
args = [[0]] + [list(range(6)) for i in range(n - 1)]
colors_iter = itertools.product(*args)
ans = 0
for c in colors_iter:
	st = set()
	for (a, value) in d.items():
		for b in value:
			st.add((max(c[a - 1], c[b - 1]), min(c[a - 1], c[b - 1])))
	ans = max(ans, len(st))
print(ans)


(n, m) = map(int, input().split())
d = []
if n < 7:
	print(m)
	exit(0)
for i in range(8):
	d.append(set())
for i in range(m):
	(a, b) = map(int, input().split())
	d[a - 1].add(b - 1)
	d[b - 1].add(a - 1)
minn = 100
for i in range(0, 7):
	for j in range(0, 7):
		ss = d[i] & d[j]
		if len(ss) < minn:
			minn = len(ss)
print(m - minn)


secondApproach = True

def calculatePossibleIncrease(setMain: set, setLeft: set, setMainIndex: int):
	directDelta = len(setMain.union(setLeft).difference(setMain.union({setMainIndex})))
	indirectDelta = len(setLeft.intersection({setMainIndex}))
	return directDelta + indirectDelta

def calculateMaxPossibleEdges(verts, leftOutVertIndex):
	tempSetEdgesCount = len(verts[leftOutVertIndex])
	retVal = -1
	for i in range(len(verts)):
		if len(verts[i]) == tempSetEdgesCount or secondApproach:
			retVal = max(retVal, calculatePossibleIncrease(verts[i], verts[leftOutVertIndex], i))
	return retVal

def calculateDirectAnswer(verts, leftOutVertIndex):
	doubleEdgeCount = 0
	for i in range(len(verts)):
		if i != leftOutVertIndex:
			doubleEdgeCount += len(verts[i].difference({leftOutVertIndex}))
	return doubleEdgeCount // 2

def main():
	(vertsCount, edgesCount) = tuple(map(int, input('').split(' ')))
	if vertsCount < 7:
		print(edgesCount)
		exit(0)
	verts = []
	for i in range(vertsCount):
		verts.append(set())
	for _t in range(edgesCount):
		(_x, _y) = tuple(map(lambda x: int(x) - 1, input('').split(' ')))
		verts[_x].add(_y)
		verts[_y].add(_x)
	edgesCount = [len(y) for y in verts]
	minEdgesCount = min(edgesCount)
	directAnswer = -1
	indirectAnswer = -1
	answer = -1
	for i in range(vertsCount):
		if len(verts[i]) == minEdgesCount or secondApproach:
			directAnswer = calculateDirectAnswer(verts, i)
			indirectAnswer = calculateMaxPossibleEdges(verts, i)
			answer = max(answer, directAnswer + indirectAnswer)
	return answer
print(main())


ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, k) = kk()
if n < 7:
	print(k)
	exit()
d = [set() for i in range(7)]
for _ in range(k):
	(a, b) = kk()
	(a, b) = (a - 1, b - 1)
	d[a].add(b)
	d[b].add(a)
maxi = 0
for a in range(7):
	for b in range(a + 1, 7):
		maxi = max(maxi, k - len(d[a] & d[b]))
print(maxi)


from collections import defaultdict
(n, m) = map(int, input().split())
graph = defaultdict(set)
for _ in range(m):
	(a, b) = map(int, input().split())
	graph[a].add(b)
	graph[b].add(a)
ans = 100
for i in range(1, 7):
	for j in range(i + 1, 8):
		g = graph[i] & graph[j]
		ans = min(ans, len(g))
print(m - ans)


import itertools
(n, m) = list(map(int, input().split()))
arr = []
for i in range(n):
	arr.append([])
for i in range(m):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	arr[a].append(b)
	arr[b].append(a)
permuts = list(itertools.permutations(list(range(7))))
ans = 0
for i in range(len(permuts)):
	permut = permuts[i]
	was = []
	for i in range(6):
		was.append([False] * 6)
	c = 0
	for i in range(n):
		if permut[i] != 6:
			for g in range(len(arr[i])):
				if not permut[arr[i][g]] == 6:
					if not was[permut[i]][permut[arr[i][g]]]:
						c += 1
						was[permut[i]][permut[arr[i][g]]] = True
						was[permut[arr[i][g]]][permut[i]] = True
	for w in range(n):
		if permut[w] == 6:
			ams = [0] * 6
			for g in range(len(arr[w])):
				for j in range(6):
					if not was[permut[arr[w][g]]][j]:
						ams[j] += 1
			c += max(ams)
			break
	ans = max(ans, c)
print(ans)


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

def ps(st, c, ans):
	if len(st) == 0:
		ans.append(tuple(c))
	nxt = set(st)
	for ci in st:
		c.append(ci)
		nxt.remove(ci)
		ps(nxt, c, ans)
		c.pop()
		nxt.add(ci)
st = set(range(6))
c = []
mine = []
ps(st, c, mine)
(n, k) = gns()
st = set()
for i in range(k):
	(a, b) = gns()
	a -= 1
	b -= 1
	(a, b) = (min(a, b), max(a, b))
	st.add((a, b))
ans = 0
for mi in mine:
	for i in range(7):
		m = mi[:i] + (0,) + mi[i:]
		nd = set()
		for i in range(7):
			for j in range(i, 7):
				ij = (i, j)
				if ij in st:
					(di, dj) = (m[i], m[j])
					(di, dj) = (min(di, dj), max(di, dj))
					nd.add((di, dj))
		l = len(nd)
		ans = max(l, ans)
print(ans)


import sys

def rint():
	return map(int, sys.stdin.readline().split())
(n, m) = rint()
ab = []
for i in range(m):
	tmp = list(rint())
	tmp.sort()
	ab.append(tmp)
d = set()
for i in range(1, 7):
	for j in range(i, 7):
		d.add((i, j))

def check_cnt():
	global max_cnt
	cnt = 0
	dd = d.copy()
	for i in range(m):
		(ai, bi) = ab[i]
		p = (num[ai], num[bi])
		if p in dd:
			dd.remove(p)
			cnt += 1
	max_cnt = max(max_cnt, cnt)
num = [0 for i in range(n + 1)]

def dfs(i, step):
	num[step] = i
	if step == n:
		check_cnt()
		return
	for j in range(7):
		dfs(j, step + 1)
max_cnt = 0
for i in range(7):
	dfs(i, 1)
print(max_cnt)


(n, m) = map(int, input().split())
d = [[] for _ in range(n + 1)]
for _ in range(m):
	(x, y) = map(int, input().split())
	d[x].append(y)
	d[y].append(x)
if n < 7:
	print(m)
else:
	max1 = -1
	for q in range(1, n):
		for q1 in range(q + 1, n + 1):
			minus = 0
			for q2 in range(1, n + 1):
				if q2 in d[q] and q2 in d[q1]:
					minus += 1
			max1 = max(max1, m - minus)
	print(max1)


(n, m) = map(int, input().split())
u = []
for i in range(n):
	u.append([])
for i in range(m):
	(a, b) = map(int, input().split())
	u[a - 1].append(b - 1)
	u[b - 1].append(a - 1)
if n < 7 or m == 0:
	print(m)
	exit()
ans = 10
for i in range(n):
	for j in range(n):
		ansi = 0
		for k in range(n):
			if i in u[k] and j in u[k]:
				ansi += 1
		ans = min(ans, ansi)
print(m - max(ans, 0))


a = list(map(int, input().split()))
n = a[0]
m = a[1]
graph = {}
for i in range(n):
	graph[i + 1] = []
for i in range(m):
	a = list(map(int, input().split()))
	graph[a[0]].append(a[1])
if n < 7:
	print(m)
else:
	res = 0
	DOMINOES = set()
	for i in range(1, 7):
		for j in range(i, 7):
			DOMINOES.add((i, j))
	max_dominoes = 0
	for i in range(7):
		for j in range(i + 1, 8):
			nums = [1, 1, 1, 1, 1, 1, 1]
			c = 2
			for k in range(len(nums)):
				if k != j and k != i:
					nums[k] = c
					c += 1
			not_used_dominoes = set(DOMINOES)
			count = 0
			ignored = 0
			for v in graph:
				for child in graph[v]:
					domino = (min(nums[v - 1], nums[child - 1]), max(nums[v - 1], nums[child - 1]))
					if domino in not_used_dominoes:
						count += 1
						not_used_dominoes.remove(domino)
			max_dominoes = max(max_dominoes, count)
			if max_dominoes >= m:
				break
	print(max_dominoes)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
vertex = [[] for j in range(7)]
for j in range(m):
	(a, b) = map(int, input().split())
	vertex[a - 1].append(b - 1)
	vertex[b - 1].append(a - 1)
most = m
if n == 7:
	maxsofar = -7
	for s in range(7):
		v0 = set(vertex[s])
		for j in range(s + 1, 7):
			v1 = set(vertex[j])
			length = len(v0.union(v1)) - (len(v0) + len(v1))
			if length > maxsofar:
				maxsofar = length
	most += maxsofar
if n <= 6:
	print(m)
else:
	print(most)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, k) = map(int, input().split())
graph = defaultdict(list)
tot = [6, 6, 6, 6, 6, 6, 6]
e = []
for i in range(k):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
	e.append((a, b))
if n <= 6:
	print(k)
	sys.exit(0)
else:
	ans = k
	for i in range(7):
		tot = set()
		for ie in range(1, 8):
			for j in range(ie, 8):
				tot.add((ie, j))
		cur = len(graph[i + 1])
		for j in range(k):
			if e[j][0] == i + 1 or e[j][1] == i + 1:
				continue
			tot.remove((min(e[j][1], e[j][0]), max(e[j][0], e[j][1])))
		check = set()
		for j in range(k):
			if e[j][0] == i + 1:
				check.add(e[j][1])
			elif e[j][1] == i + 1:
				check.add(e[j][0])
		we = 0
		for i1 in range(1, 8):
			d = 0
			if i1 == i + 1:
				continue
			for j1 in check:
				if (min(j1, i1), max(j1, i1)) in tot:
					d += 1
			we = max(we, d)
		ans = min(ans, cur - we)
	print(min(k, k - ans))


IN = input().split()
n = int(IN[0])
m = int(IN[1])
num = [0] * (n + 3)
ile = [0] * 10
E = [0] * (m + 3)
ans = 0

def spr():
	res = 0
	for b in range(1, 7):
		for a in range(1, 1 + b):
			ile[a][b] = 1
	for i in range(0, m):
		u = E[i][0]
		v = E[i][1]
		a = min(num[u], num[v])
		b = max(num[u], num[v])
		if ile[a][b] > 0:
			ile[a][b] = 0
			res += 1
	return res

def rek(N):
	if N > n:
		return spr()
	else:
		ret = 0
		for i in range(1, 7):
			num[N] = i
			ret = max(ret, rek(N + 1))
	return ret
for i in range(0, 10):
	ile[i] = [0] * 10
for i in range(0, m):
	IN = input().split()
	E[i] = [int(IN[0]), int(IN[1])]
print(rek(1))


import itertools
(n, m) = map(int, input().split())
edge = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a][b] = 1
	edge[b][a] = 1
ans = 0
d = [0] * n
for d in list(itertools.product(range(6), repeat=n)):
	count = set()
	for (i, v1) in enumerate(d):
		for (j, v2) in enumerate(d):
			if edge[i][j] == 1:
				count.add(str(v1) + str(v2))
	ans = max(len(count), ans)
print((ans + 1) // 2)


def main():
	(n, m) = map(int, input().split())
	edges = []
	for _ in range(m):
		edge = [int(x) for x in input().split()]
		if edge[0] > edge[1]:
			edge.reverse()
		edges.append(edge)
	if n < 7:
		print(m)
		return
	ecount = [0] * 8
	for (e1, e2) in edges:
		ecount[e1] += 1
		ecount[e2] += 1
	best = 0
	for i in range(1, 8):
		for j in range(1, 8):
			dom = m - ecount[i]
			if [min(i, j), max(i, j)] in edges:
				dom += 1
			for k in range(1, 8):
				if k != i and k != j and ([min(i, k), max(i, k)] in edges) and ([min(j, k), max(j, k)] not in edges):
					dom += 1
			if dom > best:
				best = dom
	print(best)
main()


def getminpair(n):
	global graph
	s = [set(graph[i]) for i in range(8)]
	inter = 100000
	ans = (-1, -1)
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if len(s[i].intersection(s[j])) < inter:
				inter = len(s[i].intersection(s[j]))
				ans = (i, j)
	return ans
(n, m) = map(int, input().split())
graph = [[], [], [], [], [], [], [], []]
for i in range(m):
	(x, y) = map(int, input().split())
	graph[x] += [y]
	graph[y] += [x]
if n <= 6:
	print(m)
	exit()
pair = getminpair(n)
s0 = set(graph[pair[0]])
s1 = set(graph[pair[1]])
print(m - len(s1.intersection(s0)))


def naiveSolve(vToDMap, edges):
	ans = 0
	dominoFree = [[False for _ in range(7)] for __ in range(7)]
	for i in range(1, 7):
		for j in range(i, 7):
			dominoFree[i][j] = True
	dCnts = 0
	for i in range(7):
		for j in range(7):
			if dominoFree[i][j]:
				dCnts += 1
	assert dCnts == 21
	for (u, v) in edges:
		(i, j) = (vToDMap[u], vToDMap[v])
		if i > j:
			temp = i
			i = j
			j = temp
		if dominoFree[i][j]:
			ans += 1
			dominoFree[i][j] = False
	return ans
from itertools import permutations

def main():
	(n, m) = readIntArr()
	edges = []
	for _ in range(m):
		edges.append(readIntArr())
	ans = 0
	for extra in range(1, 7):
		arr = list(range(1, 7)) + [extra]
		for p in permutations(arr):
			vertexToDominoMap = dict()
			p = list(p)
			for i in range(7):
				vertexToDominoMap[i + 1] = p[i]
			ans = max(ans, naiveSolve(vertexToDominoMap, edges))
	print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
lines = []
for Line in sys.stdin:
	lines.append(Line.rstrip('\n'))
(n, m) = list(map(int, lines[0].split()))
del lines[0]
G = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
	(a, b) = list(map(int, lines[i].split()))
	a = a - 1
	b = b - 1
	G[a][b] = 1
	G[b][a] = 1
if n <= 6:
	print(m)
	exit(0)
else:
	ctr = 2000000000.0
	for i in range(n):
		for k in range(n):
			temp = 0
			for j in range(n):
				if G[i][j] == 1 and G[k][j] == 1:
					temp += 1
			ctr = min(ctr, temp)
	print(m - ctr)


from sys import stdin
from collections import defaultdict
from itertools import combinations

def change_graph(define):
	temp = defaultdict(list)
	for i in graph:
		for node in graph[i]:
			temp[define[i]].append(define[node])
	return temp

def make(first, second):
	if first > second:
		(first, second) = (second, first)
	return str(first) + ' ' + str(second)

def check(arr):
	global ans
	define = dict()
	j = 0
	for i in graph:
		define[i] = arr[j]
		j += 1
	temp_graph = change_graph(define)
	visited = dict()
	for i in range(1, 7):
		for j in range(i, 7):
			visited[make(i, j)] = False
	t = 0
	for i in temp_graph:
		for node in temp_graph[i]:
			if visited[make(i, node)] == False:
				visited[make(i, node)] = True
				t += 1
	ans = max(t, ans)
(n, m) = list(map(int, stdin.readline().split()))
graph = defaultdict(list)
for _ in range(m):
	(u, v) = list(map(int, stdin.readline().split()))
	graph[u].append(v)
	graph[v].append(u)
if n <= 6:
	print(m)
	exit()
else:
	aux = []
	index = [0, 1, 2, 3, 4, 5, 6]
	total = combinations(index, 2)
	for i in total:
		temp = [0] * 7
		(first, second) = i
		temp[first] = 6
		temp[second] = 6
		i = 0
		val = 1
		while i < len(temp):
			if temp[i] == 0:
				temp[i] = val
				val += 1
			i += 1
		aux.append(temp)
ans = 0
for temp in aux:
	check(temp)
print(ans)


(n, k) = map(int, input().split())
s = [[0 for i in range(8)] for j in range(8)]
for i in range(k):
	(u, v) = map(int, input().split())
	s[u][v] = 1
	s[v][u] = 1
if n <= 6 or k == 0:
	print(k)
else:
	a = []
	for i in range(1, 8):
		for j in range(1, 8):
			if i == j:
				continue
			ct = 0
			for k in range(1, 8):
				if s[i][k] == 1 and s[j][k] == 1:
					ct += 1
			a.append([ct, i, j])
	a.sort()
	ind1 = a[0][1]
	ind2 = a[0][2]
	sum = sum1 = 0
	for i in range(1, 8):
		if s[ind1][i] == 1 and s[ind2][i] == 1:
			sum1 += 1
		elif s[ind1][i] != s[ind2][i]:
			sum1 += 1
	if s[ind1][ind2] == 1 and s[ind2][ind1] == 1:
		sum1 -= 1
	for i in range(1, 8):
		if i == ind1 or i == ind2:
			continue
		for j in range(1, 8):
			if j == ind1 or j == ind2:
				continue
			sum += s[i][j]
	print(sum1 + sum // 2)


def dfs(n):
	bool[n] = True
	for i in hash[n]:
		if bool[i] == False:
			dfs(i)
from collections import defaultdict
hash = defaultdict(set)
(n, m) = map(int, input().split())
flag = 0
for i in range(m):
	(a, b) = map(int, input().split())
	hash[a].add(b)
	hash[b].add(a)
mini = 10 ** 18
for i in range(1, 8):
	for j in range(1, 8):
		if i != j:
			mini = min(len(hash[i] & hash[j]), mini)
print(m - mini)


from collections import defaultdict
(number, mumber) = map(int, input().split())
graphical = defaultdict(set)
for _ in range(mumber):
	(a, b) = map(int, input().split())
	graphical[a].add(b)
	graphical[b].add(a)
answer = 100
for i in range(1, 7):
	for j in range(i + 1, 8):
		g = graphical[i] & graphical[j]
		answer = min(answer, len(g))
print(mumber - answer)


a = list(map(int, input().split()))
n = a[0]
m = a[1]
graph = {}
for i in range(n):
	graph[i + 1] = []
for i in range(m):
	a = list(map(int, input().split()))
	graph[a[0]].append(a[1])
if n < 7:
	print(m)
else:
	vertices = []
	for k in graph.keys():
		vertices.append((k, len(graph[k])))
	sorted_vertices = sorted(vertices, key=lambda x: x[1])
	minimum_dominoes = 0
	for i in range(1, len(sorted_vertices)):
		if sorted_vertices[0][0] in graph[sorted_vertices[i][0]]:
			minimum_dominoes += sorted_vertices[i][1] - 1
		else:
			minimum_dominoes += sorted_vertices[i][1] - 1
	res = 0
	nums = [1, 1, 1, 1, 1, 1, 1]
	DOMINOES = set()
	for i in range(1, 7):
		for j in range(i, 7):
			DOMINOES.add((i, j))
	max_dominoes = 0
	while True:
		not_used_dominoes = set(DOMINOES)
		count = 0
		ignored = 0
		for v in graph:
			for child in graph[v]:
				domino = (min(nums[v - 1], nums[child - 1]), max(nums[v - 1], nums[child - 1]))
				if domino in not_used_dominoes:
					count += 1
					not_used_dominoes.remove(domino)
				else:
					ignored += 1
					if ignored > m - minimum_dominoes:
						break
		max_dominoes = max(max_dominoes, count)
		if max_dominoes >= m:
			break
		j = len(nums) - 1
		while nums[j] == 6:
			nums[j] = 1
			j -= 1
		if j < 1:
			break
		nums[j] = nums[j] + 1
	print(max_dominoes)


(n, m) = map(int, input().split())
edges = [[int(x) - 1 for x in input().split()] for _ in range(m)]
p = [6 ** i for i in range(n)]
res = 0
for mask in range(6 ** n):
	colors = [0] + [mask // p[i] % 6 for i in range(n)]
	used = set((tuple(sorted([colors[u], colors[v]])) for (u, v) in edges))
	res = max(res, len(used))
print(res)


def DFS(x):
	visited[x] = 1
	for i in adj[x]:
		if visited[i] == 0:
			DFS(i)
l = input().split()
n = int(l[0])
m = int(l[1])
if n <= 6:
	print(m)
	quit()
adj = [[] for i in range(n)]
for i in range(m):
	l = input().split()
	u = int(l[0])
	v = int(l[1])
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
visited = [0 for i in range(n)]
DFS(0)
z = 1
for i in visited:
	if i == 0:
		z = 0
		break
if z == 0:
	print(m)
	quit()
degrees = [len(x) for x in adj]
z = min(degrees)
maxa = m - z
for i in range(7):
	for j in range(i + 1, 7):
		if i == j:
			continue
		counter = 0
		for x in adj[i]:
			if x in adj[j]:
				counter += 1
		maxa = max(maxa, m - counter)
print(maxa)


(n, m) = map(int, input().split())
lis = []
for i in range(7):
	lis.append(set())
for i in range(m):
	(a, b) = map(int, input().split())
	lis[a - 1].add(b)
	lis[b - 1].add(a)
if n <= 6:
	print(m)
else:
	ma = 1000000
	for i in range(7):
		for j in range(i + 1, 7):
			s = lis[i] & lis[j]
			if len(s) < ma:
				ma = len(s)
	print(m - ma)


from collections import defaultdict
(a, b) = map(int, input().split())
if b < 7:
	print(b)
else:
	d = defaultdict()
	for i in range(1, 8):
		d[i] = set()
	for i in range(b):
		(x, y) = map(int, input().split())
		d[x].add(y)
		d[y].add(x)
	w = 1000
	for i in range(1, 8):
		for j in range(i + 1, 8):
			s = d[i] & d[j]
			if len(s) < w:
				w = len(s)
	print(b - w)


(n, k) = list(map(int, input().split()))
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(k):
	(a, b) = list(map(int, input().split()))
	graph[a - 1][b - 1] = 1
	graph[b - 1][a - 1] = 1
ans = []
if n < 7:
	print(k)
else:
	for i in range(n):
		for j in range(i + 1, n):
			con = 0
			for p in range(n):
				if graph[i][p] == 1 and graph[j][p] == 1:
					con += 1
			ans.append(con)
	k = k - min(ans)
	print(k)


def getminpair(n):
	global graph
	s = [set(graph[i]) for i in range(8)]
	inter = 100000
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			inter = min(inter, len(s[i].intersection(s[j])))
	return inter
(n, m) = map(int, input().split())
graph = [[], [], [], [], [], [], [], []]
for i in range(m):
	(x, y) = map(int, input().split())
	graph[x] += [y]
	graph[y] += [x]
if n <= 6:
	print(m)
	exit()
print(m - getminpair(n))


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
(N, M) = map(int, input().split())
Edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
adj = [set() for _ in range(7)]
for (a, b) in Edges:
	adj[a].add(b)
	adj[b].add(a)
if N <= 6:
	ans = M
else:
	cnt = 100
	for i in range(7):
		for j in range(i + 1, 7):
			cnt = min(cnt, len(adj[i] & adj[j]))
	ans = M - cnt
print(ans)


(n, m) = [int(i) for i in input().split()]
data = []
for i in range(m):
	data.append([int(j) - 1 for j in input().split()])
ans = 0
for i in range(6 ** n):
	k = i
	num = [0] * n
	for j in range(n):
		dig = k % 6
		k //= 6
		num[j] = dig
	st = set()
	for e in data:
		t = [num[e[0]], num[e[1]]]
		if t[0] > t[1]:
			t.reverse()
		st.add(tuple(t))
	ans = max(len(st), ans)
print(ans)


from itertools import permutations

def dfs(perm, edges, ind, n):
	global dominoes
	global cur
	global tick
	if ind == n:
		tick += 1
		cnt = 0
		for (x, y) in edges:
			(a, b) = sorted((perm[x], perm[y]))
			if dominoes[a][b] and cur[a][b] < tick:
				cur[a][b] = tick
				cnt += 1
		return cnt
	else:
		ans = 0
		for i in range(6):
			perm[ind] = i
			ans = max(ans, dfs(perm, edges, ind + 1, n))
		return ans
dominoes = [[0 for i in range(6)] for i in range(6)]
cur = [[0 for i in range(6)] for i in range(6)]
tick = 0
for i in range(6):
	for j in range(i, 6):
		dominoes[i][j] = 1
(n, m) = map(int, input().split())
edges = []
for i in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	edges.append(sorted((x, y)))
perm = [0 for i in range(n)]
print(dfs(perm, edges, 0, n))


import logging
from collections import defaultdict

def calc_assigned_edge_nums(n, m, edges, new_comer):
	d_v2n = {}
	v = 1
	for i in range(1, n + 1):
		if i == new_comer:
			d_v2n[i] = 7
		else:
			d_v2n[i] = v
			v += 1
	g = defaultdict(set)
	for (a, b) in edges:
		(na, nb) = (d_v2n[a], d_v2n[b])
		g[na].add(nb)
		g[nb].add(na)
	for i in range(1, n):
		if len(g[i]) == 0:
			return m
	dominoes = {(a, b) for b in range(1, 7) for a in range(1, b + 1)}
	num_of_already_assigned_dominoes = 0
	for (vertex_from, v) in g.items():
		for vertex_to in v:
			domino = tuple(sorted([vertex_from, vertex_to]))
			if domino in dominoes:
				num_of_already_assigned_dominoes += 1
				dominoes.discard(domino)
	logging.debug('remain dominoes {}'.format(dominoes))
	max_assignable_edges_to_7 = 0
	for candidate in range(1, 7):
		num_of_assignable_edges = 0
		for vertex_from in g[7]:
			domino = tuple(sorted([vertex_from, candidate]))
			if domino in dominoes:
				num_of_assignable_edges += 1
		max_assignable_edges_to_7 = max(max_assignable_edges_to_7, num_of_assignable_edges)
	return num_of_already_assigned_dominoes + max_assignable_edges_to_7

def solve(n, m, edges=list()):
	if n <= 6:
		return m
	maximum_r = 0
	for i in range(1, n):
		r = calc_assigned_edge_nums(n, m, edges, i)
		logging.debug('#{}= {}'.format(i, r))
		maximum_r = max(maximum_r, r)
	return maximum_r
_DEBUG = False
if _DEBUG:
	logging.basicConfig(level=logging.DEBUG)
	assert solve(7, 21, [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (3, 4), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 7)]) == 16
	assert solve(4, 4, [(1, 2), (2, 3), (3, 4), (4, 1)]) == 4
	assert solve(7, 0) == 0
	assert solve(3, 1, [(1, 3)]) == 1
else:
	logging.basicConfig(level=logging.WARN)
(_n, _m) = map(int, input().split())
_edges = []
for _ in range(_m):
	(a, b) = map(int, input().split())
	_edges.append([a, b])
print(solve(_n, _m, _edges))


def dominoes(n, m, edges):
	if n <= 6:
		return m
	if m == 0:
		return 0
	mscore = 7
	for a in range(1, 7):
		for b in range(a):
			score = codeg(a, b, edges)
			if score < mscore:
				mscore = score
	return m - mscore

def codeg(a, b, edges):
	c = 0
	for x in range(7):
		if x == a:
			continue
		if x == b:
			continue
		if [a, x] in edges or [x, a] in edges:
			if [b, x] in edges or [x, b] in edges:
				c += 1
	return c
(n, m) = map(int, input().split())
ed = []
for x in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	ed.append([a, b])
print(dominoes(n, m, ed))


from itertools import product
(n, m) = map(int, input().split())
e = []
for i in range(m):
	(a, b) = map(int, input().split())
	e.append((a, b))
ans = 0
for idx in product([0], *[list(range(1, 7)) for i in range(n)]):
	used = [[0] * 7 for i in range(7)]
	cnt = 0
	for (u, v) in e:
		(u, v) = (idx[u], idx[v])
		(u, v) = (min(u, v), max(u, v))
		if not used[u][v]:
			used[u][v] = 1
			cnt += 1
	ans = max(ans, cnt)
print(ans)


(n, m) = input().split()
(n, m) = (int(n), int(m))
edges = [[] for x in range(n)]
for i in range(m):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	ma = max(a, b)
	mi = min(a, b)
	edges[mi - 1].append(ma - 1)
	edges[ma - 1].append(mi - 1)
xxx = []
if n <= 6:
	print(m)
else:
	for i in range(n):
		for j in range(i):
			xxx.append(set(edges[i]).intersection(set(edges[j])))
	p = [len(z) for z in xxx]
	print(m - min(p))


from itertools import product
(n, m) = map(int, input().split())
node = [0, 1, 2, 3, 4, 5, 6]
node = node[:n]
g = []
for _ in range(m):
	(a, b) = map(int, input().split())
	g.append((a - 1, b - 1))
ans = 0
for pp in product(node, repeat=n):
	D = [[False] * 7 for _ in range(7)]
	for i in range(7):
		D[6][i] = D[i][6] = True
	cnt = 0
	cnt2 = 0
	h = -1
	if 6 in pp:
		h = pp.index(6)
	for (a, b) in g:
		if a == h or b == h:
			cnt2 += 1
		if not D[pp[a]][pp[b]]:
			D[pp[a]][pp[b]] = True
			D[pp[b]][pp[a]] = True
			cnt += 1
	if cnt2:
		cnt += 1
	ans = max(ans, cnt)
print(ans)


def main():
	(n, m) = map(int, input().split())
	Edges = [[] for _ in range(7)]
	for _ in range(m):
		(a, b) = map(lambda x: int(x) - 1, input().split())
		Edges[a].append(b)
		Edges[b].append(a)
	if n <= 6:
		return m
	cnt = 6
	for i in range(6):
		for j in range(i + 1, 7):
			cnt = min(cnt, len(set(Edges[i]) & set(Edges[j])))
	return m - cnt
print(main())


from math import *
from collections import *
from bisect import *
import sys
input = sys.stdin.readline
t = 1
while t:
	t -= 1
	(n, k) = map(int, input().split())
	deg = [set() for i in range(n)]
	for i in range(k):
		(u, v) = map(int, input().split())
		deg[u - 1].add(v - 1)
		deg[v - 1].add(u - 1)
	if n <= 6:
		print(k)
	else:
		ma = 0
		for i in range(7):
			for j in range(i + 1, 7):
				ma = max(ma, k - len(deg[i] & deg[j]))
		print(ma)


n = list(map(int, input().split()))
e = n[1]
n = n[0]
d = {}
for itr in range(1, n + 1):
	d[itr] = []
for i in range(e):
	a = list(map(int, input().split()))
	d[a[0]].append(a[1])
	d[a[1]].append(a[0])
if n <= 6:
	print(e)
else:
	asdf = []
	for ii in range(1, 8):
		ans = e - len(d[ii])
		if ii != 7:
			(d[ii], d[7]) = (d[7], d[ii])
			for i in d:
				for j in range(len(d[i])):
					if d[i][j] == ii:
						d[i][j] = 7
					elif d[i][j] == 7:
						d[i][j] = ii
		domino = [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6), (5, 5), (5, 6), (6, 6)]
		for i in range(1, 7):
			for j in d[i]:
				if j == 7 or j < i:
					continue
				else:
					domino.remove((i, j))
		for i in domino:
			if i[0] in d[7] or i[1] in d[7]:
				continue
			else:
				domino.remove(i)
		dd = {}
		possible = 0
		for i in range(1, 7):
			count = 0
			for itr in domino:
				if itr[0] == i:
					if itr[1] in d[7]:
						count += 1
				elif itr[1] == i:
					if itr[0] in d[7]:
						count += 1
			possible = max(count, possible)
		asdf.append(ans + possible)
	print(max(asdf))


import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
sys.setrecursionlimit(200000)
import itertools
input = sys.stdin.readline

def ii():
	return int(input())

def mi():
	return map(int, input().rstrip().split())

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

def fi():
	return float(input())

def mfi():
	return map(float, input().rstrip().split())

def lmfi():
	return list(map(float, input().rstrip().split()))

def li():
	return list(input().rstrip())

def debug(*args, sep=' ', end='\n'):
	print('debug:', *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None

def exit(*arg):
	print(*arg)
	sys.exit()

class Graph:

	def __init__(self, n, Weighted=False, Directed=True, Matrix=False):
		self.sz = n
		self.is_Weighted = Weighted
		self.is_Directed = Directed
		self.is_Matrix = Matrix
		if Matrix:
			if Weighted:
				self.graph = [[0 for _i in range(n)] for _j in range(n)]
			else:
				self.graph = [[0 for _i in range(n)] for _j in range(n)]
		else:
			self.graph = [[] for _i in range(n)]

	def _weighted_add_edge(self, x, y, w):
		if self.is_Matrix:
			self.graph[x][y] = w
		else:
			self.graph[x].append((y, w))

	def _unweighted_add_edge(self, x, y):
		if self.is_Matrix:
			self.graph[x][y] = 1
		else:
			self.graph[x].append(y)

	def add_edge(self, x, y, *w):
		if self.is_Directed:
			if self.is_Weighted:
				self._weighted_add_edge(x, y, w[0])
			else:
				self._unweighted_add_edge(x, y)
		elif self.is_Weighted:
			self._weighted_add_edge(x, y, w[0])
			self._weighted_add_edge(y, x, w[0])
		else:
			self._unweighted_add_edge(x, y)
			self._unweighted_add_edge(y, x)

def main():
	(n, m) = mi()
	t = Graph(n, Directed=False)
	la = 0
	for i in range(m):
		(a, b) = mi()
		(a, b) = (a - 1, b - 1)
		t.add_edge(a, b)
	for l in itertools.product(range(6), repeat=n):
		d = [[0 for i in range(6)] for j in range(6)]
		for i in range(n):
			for j in t.graph[i]:
				d[l[i]][l[j]] = 1
		ans = sum((sum(d[i][0:i + 1]) for i in range(6)))
		la = max(ans, la)
	print(la)
	return
main()


(n, m) = map(int, input().split())
l = [[] for _ in range(n)]
for i in range(m):
	(k, p) = map(int, input().split())
	l[k - 1].append(p)
	l[p - 1].append(k)
if n < 7 or m == 0:
	print(m)
else:
	k = [len(l[i]) for i in range(n)]
	mi = 9999
	for i in range(n):
		for j in range(i + 1, n):
			x = len(set(l[i]).union(set(l[j])))
			x = k[i] + k[j] - x
			if mi > x:
				mi = x
	print(m - mi)


from itertools import *
(n, m) = map(int, input().split())
e = [tuple((int(s) - 1 for s in input().split())) for _ in range(m)]
print(max((len(set((tuple(sorted([p[a], p[b]])) for (a, b) in e))) for p in permutations((i % 6 for i in range(n))))))


edges = []
(n, m) = map(lambda x: int(x), input().split())
for i in range(m):
	curr = [0, 0]
	(curr[0], curr[1]) = map(lambda x: int(x) - 1, input().split())
	edges.append(curr)
num_in = [1, 1, 1, 1, 1, 1, 1]
abs_max = 0
c = 0
for num_in[1] in range(1, 7):
	for num_in[2] in range(1, 7):
		for num_in[3] in range(1, 7):
			for num_in[4] in range(1, 7):
				for num_in[5] in range(1, 7):
					for num_in[6] in range(1, 7):
						c += 1
						used = []
						curr_max = 0
						for x in edges:
							crr = [num_in[x[0]], num_in[x[1]]]
							if crr[0] > crr[1]:
								(crr[0], crr[1]) = (crr[1], crr[0])
							if crr in used:
								continue
							used.append(crr)
							curr_max += 1
						abs_max = max(abs_max, curr_max)
						if abs_max == m:
							print(m)
							exit()
print(abs_max)


(n, m) = map(int, input().split())
edge = [[0] * 10 for _i in range(10)]
cnt = [0] * 10
for i in range(m):
	(a, b) = map(int, input().split())
	edge[a][b] = edge[b][a] = 1
	cnt[a] += 1
	cnt[b] += 1
if n <= 6:
	print(m)
	exit(0)
ans = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		if i == j:
			continue
		ct = 0
		for k in range(1, n + 1):
			if edge[i][k] and edge[j][k]:
				ct += 1
		ans = max(ans, m - ct)
print(ans)


(n, m) = map(int, input().split())
G = [[] for i in range(n)]
ans = 0
for i in range(m):
	(u, v) = map(int, input().split())
	G[u - 1].append(v - 1)
	G[v - 1].append(u - 1)
minus = 2333
if n <= 6:
	ans = m
else:
	for i in range(7):
		for j in range(i + 1, 7):
			cnt = 0
			for q in range(7):
				if q in G[i] and q in G[j]:
					cnt += 1
			minus = min(minus, cnt)
	ans = m - minus
print(ans)