Do you know a story about the three musketeers? Anyway, you will learn about its origins now.

Richelimakieu is a cardinal in the city of Bearis. He is tired of dealing with crime by himself. He needs three brave warriors to help him to fight against bad guys.

There are n warriors. Richelimakieu wants to choose three of them to become musketeers but it's not that easy. The most important condition is that musketeers must know each other to cooperate efficiently. And they shouldn't be too well known because they could be betrayed by old friends. For each musketeer his recognition is the number of warriors he knows, excluding other two musketeers.

Help Richelimakieu! Find if it is possible to choose three musketeers knowing each other, and what is minimum possible sum of their recognitions.


-----Input-----

The first line contains two space-separated integers, n and m (3 ≤ n ≤ 4000, 0 ≤ m ≤ 4000) — respectively number of warriors and number of pairs of warriors knowing each other.

i-th of the following m lines contains two space-separated integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}). Warriors a_{i} and b_{i} know each other. Each pair of warriors will be listed at most once.


-----Output-----

If Richelimakieu can choose three musketeers, print the minimum possible sum of their recognitions. Otherwise, print "-1" (without the quotes).


-----Examples-----
Input
5 6
1 2
1 3
2 3
2 4
3 4
4 5

Output
2

Input
7 4
2 1
3 6
5 1
1 7

Output
-1



-----Note-----

In the first sample Richelimakieu should choose a triple 1, 2, 3. The first musketeer doesn't know anyone except other two musketeers so his recognition is 0. The second musketeer has recognition 1 because he knows warrior number 4. The third musketeer also has recognition 1 because he knows warrior 4. Sum of recognitions is 0 + 1 + 1 = 2.

The other possible triple is 2, 3, 4 but it has greater sum of recognitions, equal to 1 + 1 + 1 = 3.

In the second sample there is no triple of warriors knowing each other.

Difficulty: MEDIUM
Tags: String algorithms

Graph algorithms

Graph traversal

Complete search
Skill types: Complete search

Starter code:

Solutions:
(qtdWarriors, pares) = input().split()
qtdWarriors = int(qtdWarriors)
pares = int(pares)
dic = {}
somas = []
for i in range(pares):
	(chave, valor) = input().split()
	if chave not in dic:
		dic[chave] = [valor]
	else:
		dic[chave].append(valor)
	if valor not in dic:
		dic[valor] = [chave]
	else:
		dic[valor].append(chave)
for key in dic:
	for e in dic[key]:
		if e in dic:
			for e2 in dic[e]:
				if e2 in dic[key] and e2 in dic[e] and (key in dic[e2]) and (key in dic[e]) and (e in dic[e2]):
					soma = len(dic[key]) + len(dic[e])
					soma += len(dic[e2])
					somas.append(soma - 6)
if somas != []:
	print(min(somas))
else:
	print(-1)


ans = -1
edge = list()
(n, m) = map(int, input().split())
s = [set() for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	edge += [(u, v)]
	s[u] |= {v}
	s[v] |= {u}
k = [len(s[i]) for i in range(n + 1)]
for (u, v) in edge:
	w = s[u] & s[v]
	for i in w:
		res = k[u] + k[v] + k[i] - 6
		if ans == -1 or ans > res >= 0:
			ans = res
print(ans)


def calculaVizinhos(grafo):
	ciclos = []
	for vertice in grafo:
		for destino1 in grafo[vertice]:
			ciclo = [vertice, destino1]
			for destino2 in grafo[vertice]:
				if destino2 in grafo[destino1]:
					ciclo.append(destino2)
					ciclos.append(ciclo)
					ciclo = [vertice, destino1]
	menor_conhecimento = -1
	for ciclo in ciclos:
		total = sum(list(map(lambda x: len(grafo[x]), ciclo)))
		if total < menor_conhecimento or menor_conhecimento == -1:
			menor_conhecimento = total
	if menor_conhecimento != -1:
		menor_conhecimento = menor_conhecimento - 6
	return menor_conhecimento
(n, m) = map(int, input().split())
grafo = {}
for i in range(1, n + 1):
	grafo[i] = []
for i in range(m):
	(origem, destino) = map(int, input().split())
	grafo[origem].append(destino)
	grafo[destino].append(origem)
print(calculaVizinhos(grafo))


from sys import stdin, stdout
(n, m) = map(int, input().split())
from collections import defaultdict
edges = defaultdict(set)
l = 1000000000.0
for i in range(m):
	(c, d) = (int(o) for o in stdin.readline().split())
	edges[c].add(d)
	edges[d].add(c)
for v in edges.values():
	for second in v:
		for third in v:
			if third in edges[second]:
				reg = len(edges[third]) + len(edges[second]) + len(v) - 6
				if reg >= 0:
					l = min(l, reg)
if l == 1000000000.0:
	exit(print(-1))
print(l)


(n, m) = map(int, input().split())
d = [[] for i in range(n)]
f = [0] * n
for i in range(m):
	a = list(map(int, input().split()))
	f[a[0] - 1] += 1
	f[a[1] - 1] += 1
	a.sort()
	d[a[1] - 1] += [a[0]]
ans = []
for i in range(n):
	d[i].sort()
	d[i].reverse()
	for j in d[i]:
		for k in d[i]:
			if k in d[j - 1]:
				res = f[k - 1] - 2 + f[j - 1] - 2 + f[i] - 2
				ans += [res]
if ans:
	print(min(ans))
else:
	print('-1')


(n, m) = [int(x) for x in input().split()]
friends = [set() for i in range(n + 1)]
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	friends[a].add(b)
	friends[b].add(a)
recognition = []
for i in range(n + 1):
	recognition.append(len(friends[i]))
total = []
for i in range(n - 1):
	for j in range(i, n):
		if i in friends[j]:
			for k in range(j, n + 1):
				if i in friends[k] and j in friends[k]:
					total.append(recognition[i] + recognition[j] + recognition[k] - 6)
if total:
	print(min(total))
else:
	print(-1)


import bisect
import decimal
from decimal import Decimal
import os
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate
decimal.getcontext().prec = 46

def primeFactors(n):
	prime = set()
	while n % 2 == 0:
		prime.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			prime.add(i)
			n = n // i
	if n > 2:
		prime.add(n)
	return list(prime)

def getFactors(n):
	factors = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				factors.append(i)
			else:
				factors.append(i)
				factors.append(n // i)
		i = i + 1
	return factors

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	num = []
	for p in range(2, n + 1):
		if prime[p]:
			num.append(p)
	return num

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

def sort_dict(key_value):
	return sorted(key_value.items(), key=lambda kv: (kv[1], kv[0]))

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

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

def string_list():
	return list(input())

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def binaryToDecimal(n):
	return int(n, 2)

def DFS(n, s, adj):
	visited = [False for i in range(n)]
	stack = []
	stack.append(s)
	while len(stack):
		s = stack[-1]
		stack.pop()
		if not visited[s]:
			visited[s] = True
		for node in adj[s]:
			if not visited[node]:
				stack.append(node)

def solve():
	(n, m) = num_input()
	adj_list = {}
	for _ in range(m):
		(u, v) = num_input()
		try:
			adj_list[u].add(v)
		except KeyError:
			adj_list[u] = {v}
		try:
			adj_list[v].add(u)
		except KeyError:
			adj_list[v] = {u}
	ans = 10 ** 10
	for i in adj_list.keys():
		for j in adj_list[i]:
			nodes = list(adj_list[i].intersection(adj_list[j]))
			if nodes != []:
				temp = 10 ** 10
				for k in nodes:
					temp = min(temp, len(adj_list[k]))
				temp += len(adj_list[i]) + len(adj_list[j]) - 6
				ans = min(ans, temp)
	if ans == 10 ** 10:
		print(-1)
	else:
		print(ans)
t = 1
for _ in range(t):
	solve()


from sys import stdin, stdout
input = stdin.readline
(n, m) = map(int, input().split())
graph = [set([]) for _ in range(n)]
popularity = [0 for _ in range(n)]
connections = []
for _ in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	graph[x].add(y)
	graph[y].add(x)
	popularity[x] += 1
	popularity[y] += 1
	connections.append((x, y))
best = 100500
for (x, y) in connections:
	for el in graph[x] & graph[y]:
		best = min(popularity[x] + popularity[y] + popularity[el] - 6, best)
if best == 100500:
	stdout.write('-1')
else:
	stdout.write(str(best))


(n, m) = map(int, input().split())
n += 1
(vv, cnt, res) = ([set() for i in range(n)], [0] * n, [])
for i in range(m):
	(a, b) = map(int, input().split())
	for c in vv[a].intersection(vv[b]):
		res.append((a, b, c))
	vv[a].add(b)
	vv[b].add(a)
	cnt[a] += 1
	cnt[b] += 1
f = cnt.__getitem__
print(min((sum(map(f, i)) for i in res)) - 6 if res else '-1')


(n, m) = list(map(int, input().split()))
g = [set() for _ in range(n)]
l = []
p = [0 for _ in range(n)]
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	p[a] += 1
	p[b] += 1
	g[a].add(b)
	g[b].add(a)
	l.append((a, b))
ans = 100000
for (i, j) in l:
	for k in range(n):
		if k in g[i] and k in g[j]:
			ans = min(ans, p[i] + p[j] + p[k])
if ans == 100000:
	ans = -1
else:
	ans -= 6
print(ans)


(n, m) = map(int, input().split())
gr = [set() for _ in range(n)]
deg = [0] * n
ans = 10 ** 10
edg = [None] * m
for i in range(m):
	(a, b) = map(int, input().split())
	gr[a - 1].add(b - 1)
	gr[b - 1].add(a - 1)
	deg[a - 1] += 1
	deg[b - 1] += 1
	edg[i] = (a - 1, b - 1)
for (t, t1) in edg:
	if deg[t] > deg[t1]:
		(t, t1) = (t1, t)
	for j in gr[t]:
		if j in gr[t1]:
			ans = min(ans, deg[t] + deg[t1] + deg[j] - 6)
print(ans if ans != 10 ** 10 else -1)


(n, m) = [int(i) for i in input().split(' ')]
graph = {}
for _ in range(m):
	node = [int(i) for i in input().split(' ')]
	graph.setdefault(node[0], set())
	graph[node[0]].add(node[1])
	graph.setdefault(node[1], set())
	graph[node[1]].add(node[0])
options = set()
for i in graph:
	if len(graph[i]) >= 2:
		for j in graph[i]:
			if len(graph[j]) >= 2:
				for k in graph[j]:
					if i in graph[j] and j in graph[k] and (k in graph[i]):
						options.add(tuple(sorted([i, j, k])))
minimum = 4000 * 3
if options:
	for option in options:
		minimum = min(minimum, len(graph[option[0]]) + len(graph[option[1]]) + len(graph[option[2]]) - 6)
	print(minimum)
else:
	print(-1)


(n, m) = [int(x) for x in input().split()]
g = [[False] * n for i in range(n)]
grau = [0] * n
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	g[a][b] = g[b][a] = True
	grau[a] += 1
	grau[b] += 1
ans = 10 ** 8
for i in range(n):
	for j in range(i + 1, n):
		if g[i][j]:
			for k in range(j + 1, n):
				if g[i][k] and g[j][k]:
					ans = min(ans, grau[i] + grau[j] + grau[k])
if ans != 10 ** 8:
	print(ans - 6)
else:
	print('-1')


(n, m) = map(int, input().split())
gr = [set() for _ in range(n)]
deg = [0 for i in range(n)]
ans = 10 ** 10
for _ in range(m):
	(a, b) = map(int, input().split())
	gr[a - 1].add(b - 1)
	gr[b - 1].add(a - 1)
	deg[a - 1] += 1
	deg[b - 1] += 1
for i in range(n):
	if deg[i] < 2:
		continue
	for j in gr[i]:
		for k in gr[i]:
			if j in gr[k]:
				ans = min(ans, deg[i] + deg[j] + deg[k] - 6)
print(ans if ans != 10 ** 10 else -1)


(n, m) = [int(i) for i in input().split()]
vertice = [set() for i in range(n + 1)]
for i in range(m):
	(src, dest) = [int(i) for i in input().split()]
	vertice[src].add(dest)
	vertice[dest].add(src)
vistoPar = {}
minSum = float('inf')
for i in range(1, n + 1):
	for j in vertice[i]:
		a = str(i) + str(j)
		b = str(j) + str(i)
		if a in vistoPar or b in vistoPar:
			continue
		terceiros = vertice[i].intersection(vertice[j])
		for k in terceiros:
			soma = len(vertice[i]) + len(vertice[j])
			soma += len(vertice[k]) - 6
			minSum = min(minSum, soma)
		vistoPar[a] = 1
		vistoPar[b] = 1
if minSum == float('inf'):
	print(-1)
else:
	print(minSum)


(n, m) = list(map(int, input().split()))
ma = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	ma[a].append(b)
	ma[b].append(a)
min_ = 999999

def rec(a, b=None, c=None):
	r1 = len(ma[a]) - 2
	r2 = len(ma[b]) - 2 if b else 0
	r3 = len(ma[c]) - 2 if c else 0
	return r1 + r2 + r3
for i in range(1, n + 1):
	if rec(i) < 0:
		continue
	for j in ma[i]:
		if rec(j) < 0:
			continue
		for k in ma[j]:
			if k in ma[i]:
				r = rec(i, j, k)
				if r < min_:
					min_ = r
if min_ != 999999:
	print(min_)
else:
	print(-1)


(n, m) = map(int, input().split())
INF = float('inf')
graph = []
for i in range(n):
	graph.append(set())
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].add(b)
	graph[b].add(a)
candidates = set()
for i in range(n):
	if len(graph[i]) >= 2:
		candidates.add(i)
ans = INF
for i in candidates:
	for j in graph[i]:
		if j not in candidates:
			continue
		for k in graph[j]:
			if k not in candidates:
				continue
			if i in graph[k]:
				ans = min(ans, len(graph[i]) + len(graph[j]) + len(graph[k]) - 6)
if ans < INF:
	print(ans)
else:
	print(-1)


(n, m) = map(int, input().split())
a = [0] * (n + 1)
b = [[0] * (n + 1) for i in range(n + 1)]
l = 1000000000.0
for i in range(m):
	(c, d) = map(int, input().split())
	a[c] += 1
	a[d] += 1
	b[c][d] += 1
	b[d][c] += 1
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if b[i][j]:
			for k in range(j + 1, n + 1):
				if b[j][k] and b[k][i]:
					l = min(l, a[i] + a[j] + a[k] - 6)
if l == 1000000000.0:
	exit(print(-1))
print(l)


(n, m) = (int(i) for i in input().split())
c = {}
b = [0] * (n + 1)
q = 10000000
for j in range(m):
	(a, g) = (int(i) for i in input().split())
	if a in list(c.keys()):
		c[a].append(g)
	else:
		c[a] = [g]
	if g in list(c.keys()):
		c[g].append(a)
	else:
		c[g] = [a]
	b[a] = b[a] + 1
	b[g] = b[g] + 1
for first in list(c.keys()):
	for second in c[first]:
		if first > second:
			for third in c[second]:
				if third in c[first] and third != first and (second > third):
					if q > b[third] + b[second] + b[first] - 6:
						q = b[third] + b[second] + b[first] - 6
if q == 10000000:
	print(-1)
else:
	print(q)


from collections import defaultdict
from itertools import combinations
read_many = lambda type_: list(map(type_, input().split()))

def main():
	(n, m) = read_many(int)
	relations = defaultdict(lambda : {})
	d = {}
	for i in range(m):
		(w1, w2) = read_many(int)
		relations[w1][w2] = 0
		relations[w2][w1] = 0
	(lowest_rec, know_each_other_penalty) = (float('inf'), 6)
	for w1 in range(1, n + 1):
		w1_k = relations[w1].keys()
		w1_rec = len(w1_k)
		if w1_rec >= 2:
			for w2 in w1_k:
				w2_k = set(relations[w2].keys())
				w2_rec = len(w2_k)
				common_friends = set(w1_k).intersection(w2_k)
				for w3 in common_friends:
					rec_group = w1_rec + w2_rec + len(relations[w3]) - know_each_other_penalty
					if rec_group < lowest_rec:
						lowest_rec = rec_group
	print(-1 if lowest_rec == float('inf') else lowest_rec)
main()


from sys import stdin, stdout
input = stdin.readline
(n, m) = map(int, input().split())
graph = [set([]) for i in range(n + 1)]
popularity = [0 for i in range(n + 1)]
connections = []
for _ in range(m):
	(x, y) = map(int, input().split())
	graph[x].add(y)
	graph[y].add(x)
	connections.append((x, y))
	popularity[x] += 1
	popularity[y] += 1
best = 1000000000.0
for (x, y) in connections:
	d = [0] * (n + 1)
	for i in graph[x]:
		d[i] = 1
	for i in graph[y]:
		if d[i] == 1:
			best = min(best, popularity[x] + popularity[y] + popularity[i] - 6)
if best == 1000000000.0:
	best = -1
stdout.write(str(best))


(n, m) = map(int, input().split())
aux = m
graph = [[] for j in range(n + 1)]
while aux > 0:
	(e1, e2) = map(int, input().split())
	graph[e1].append(e2)
	graph[e2].append(e1)
	aux = aux - 1
minimum = n * 3
for i in range(1, n - 1):
	if len(graph[i]) < 2:
		continue
	else:
		for e in graph[i]:
			if len(graph[e]) < 2:
				continue
			else:
				for z in graph[e]:
					if z in graph[i]:
						temp = len(graph[i]) + len(graph[e]) + len(graph[z]) - 6
						if temp < minimum:
							minimum = temp
if minimum < n * 3:
	print(minimum)
else:
	print(-1)


read = lambda : map(int, input().split())
(n, m) = read()
G = [set() for i in range(n + 1)]
S = [0 for i in range(n + 1)]
for i in range(m):
	(a, b) = read()
	G[a].add(b)
	G[b].add(a)
	S[a] += 1
	S[b] += 1
ans = 10 ** 10
for i in range(1, n + 1):
	for j in G[i]:
		for k in G[j]:
			if i in G[k]:
				x = S[i] + S[j] + S[k] - 6
				ans = min(x, ans)
if ans == 10 ** 10:
	ans = -1
print(ans)


from collections import defaultdict, deque
(n, m) = [int(i) for i in input().split()]
g = defaultdict(set)
edges = []
for i in range(m):
	(f, s) = [int(j) for j in input().split()]
	edges.append((f, s))
	g[f].add(s)
	g[s].add(f)
triangles = set()
for e in edges:
	(f, s) = e
	i = g[f] & g[s]
	if len(i) > 0:
		for common in i:
			triangles.add(tuple(sorted([f, s, common])))
if len(triangles) == 0:
	print(-1)
else:
	min_rec = None
	for t in triangles:
		rec = len(g[t[0]]) + len(g[t[1]]) + len(g[t[2]])
		if min_rec is None or rec < min_rec:
			min_rec = rec
	print(min_rec - 6)


def main():
	from bisect import bisect
	(n, m) = map(int, input().split())
	l = [[] for _ in range(n + 1)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		l[a].append(b)
		l[b].append(a)
	for la in l:
		la.sort()
	res = []
	for (a, la) in enumerate(l):
		le = len(la)
		for i in range(bisect(la, a), le - 1):
			b = la[i]
			for j in range(i + 1, le):
				c = la[j]
				if c in l[b]:
					res.append(le + len(l[b]) + len(l[c]))
	print(min(res) - 6 if res else -1)
main()


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
(n, m) = (int(i) for i in input().split())
adj = [[0 for i in range(n)] for j in range(n)]
deg = [0 for i in range(n)]
for i in range(m):
	(u, v) = (int(i) for i in input().split())
	adj[u - 1][v - 1] = 1
	adj[v - 1][u - 1] = 1
	deg[u - 1] += 1
	deg[v - 1] += 1
ans = 10000000
for i in range(n):
	for j in range(i + 1, n):
		if adj[i][j] == 1:
			for k in range(j + 1, n):
				if adj[i][k] == 1 and adj[j][k] == 1:
					ans = min(ans, deg[i] + deg[j] + deg[k] - 6)
if ans == 10000000:
	print(-1)
else:
	print(ans)


import sys
inf = float('inf')
sys.setrecursionlimit(100000)

class Graph(object):

	def __init__(self, v):
		self.edges = {}
		self.vertex_map = [[False for j in range(v + 1)] for i in range(v + 1)]

	def add_edge(self, u, v):
		(edges, vertex_map) = (self.edges, self.vertex_map)
		if not u in edges:
			edges[u] = []
		if not v in edges:
			edges[v] = []
		edges[u].append(v)
		edges[v].append(u)
		vertex_map[u][v] = vertex_map[v][u] = True

	def has_edge(self, u, v):
		(edges, vertex_map) = (self.edges, self.vertex_map)
		return self.vertex_map[u][v]

	def adj(self, u):
		(edges, vertex_map) = (self.edges, self.vertex_map)
		return [] if not u in edges else edges[u]

def dfs(graph, u, visited, rps):
	adju = graph.adj(u)
	ret = inf
	if len(adju) == 0 or visited[u]:
		return ret
	visited[u] = True
	for v in adju:
		if visited[v]:
			continue
		r = dfs(graph, v, visited, rps)
		if ret > r:
			ret = r
	for v in adju:
		ae = set(adju) & set(graph.adj(v)) - set([u, v])
		if len(ae) == 0:
			continue
		for p in ae:
			if not visited[v]:
				continue
			if ret > rps[u] + rps[v] + rps[p] - 6:
				ret = rps[u] + rps[v] + rps[p] - 6
	return ret

def algo():
	(vc, lc) = [int(i) for i in input().split(' ')]
	graph = Graph(vc)
	rps = [0 for i in range(vc + 1)]
	for i in range(1, lc + 1):
		(u, v) = [int(i) for i in input().split(' ')]
		graph.add_edge(u, v)
		rps[u] += 1
		rps[v] += 1
	ret = inf
	visited = [False for i in range(vc + 1)]
	for u in range(1, vc + 1):
		r = dfs(graph, u, visited, rps)
		if ret > r:
			ret = r
	if ret == inf:
		ret = -1
	print(ret)
algo()


(n, m) = (int(x) for x in input().split())
adj = [0] * n
for i in range(n):
	adj[i] = []
for i in range(m):
	(a, b) = (int(x) for x in input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
best = 1000000
for i in range(n):
	cur_set = set(adj[i])
	for j in adj[i]:
		for k in adj[j]:
			if k in cur_set:
				best = min(best, len(adj[i]) + len(adj[j]) + len(adj[k]) - 6)
if best == 1000000:
	best = -1
print(best)


(n, m) = [int(i) for i in input().split()]
v = [set() for i in range(n + 1)]
for i in range(m):
	(x, y) = [int(i) for i in input().split()]
	v[x].add(y)
	v[y].add(x)
vp = {}
start = 10 ** 10000
result = start
for i in range(1, n + 1):
	for j in v[i]:
		a = str(i) + str(j)
		b = str(j) + str(i)
		if a in vp or b in vp:
			continue
		terceiros = v[i].intersection(v[j])
		for k in terceiros:
			soma = len(v[i]) + len(v[j])
			soma += len(v[k]) - 6
			result = min(result, soma)
		vp[a] = 1
		vp[b] = 1
if result == start:
	print(-1)
else:
	print(result)


(n, m) = map(int, input().split())
g = [set() for i in range(n)]
e = []
res = 10 ** 10000
l = [0] * n
for i in range(m):
	a = tuple(map(int, input().split()))
	a = (a[0] - 1, a[1] - 1)
	e.append(a)
	g[a[0]].add(a[1])
	g[a[1]].add(a[0])
for i in range(n):
	l[i] = len(g[i])
for i in range(m):
	a = e[i][0]
	b = e[i][1]
	c = g[a] & g[b]
	for f in c:
		res = min(res, l[a] + l[b] + l[f] - 6)
if res != 10 ** 10000:
	print(res)
else:
	print(-1)


(n, m) = [int(index) for index in input().split()]
v = [set() for index in range(n + 1)]
for index in range(m):
	(x, y) = [int(index) for index in input().split()]
	v[x].add(y)
	v[y].add(x)
vp = {}
initalValue = 10 ** 10000
resultSum = initalValue
for index in range(1, n + 1):
	for j in v[index]:
		a = str(index) + str(j)
		b = str(j) + str(index)
		if a in vp or b in vp:
			continue
		terceiros = v[index].intersection(v[j])
		for k in terceiros:
			soma = len(v[index]) + len(v[j])
			soma += len(v[k]) - 6
			resultSum = min(resultSum, soma)
		vp[a] = 1
		vp[b] = 1
if resultSum == initalValue:
	print(-1)
else:
	print(resultSum)


__author__ = 'Juan Barros'
inf = 9999999999
(n, m) = list(map(int, input().split()))
degree = [0] * (n + 1)
M = [[False] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	M[a][b] = True
	M[b][a] = True
	degree[a] += 1
	degree[b] += 1
result = inf
for i in range(n + 1):
	for j in range(n + 1):
		if M[i][j]:
			for k in range(j + 1, n + 1):
				if M[i][k] and M[j][k]:
					result = min(result, degree[i] + degree[j] + degree[k])
print(-1 if result == inf else result - 6)


from sys import stdin, stdout
from collections import defaultdict
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	g = defaultdict(set)
	(n, eg) = lst()
	ans = float('inf')
	for i in range(eg):
		(u, v) = lst()
		g[u].add(v)
		g[v].add(u)
	for a in range(1, n + 1):
		for b in g[a]:
			for c in g[a] & g[b]:
				ans = min(ans, len(g[a]) + len(g[b]) + len(g[c]) - 6)
	print(ans if ans != float('inf') else -1)


import sys
import io
from collections import defaultdict
from itertools import combinations

def solve(n, m, pairs):
	assert 3 <= n <= 4000
	assert 0 <= m <= 4000
	recognitions = defaultdict(set)
	for (a, b) in pairs:
		recognitions[a].add(b)
		recognitions[b].add(a)
	minr = float('inf')
	for (candidate, recognition) in [(c, rs) for (c, rs) in list(recognitions.items()) if len(rs) > 1]:
		for (c2, c3) in [(a, b) for (a, b) in combinations(recognition, 2) if a in recognitions[b]]:
			sum_r = sum([len(recognitions[x]) for x in [candidate, c2, c3]])
			minr = min([sum_r, minr])
	if minr == float('inf'):
		return -1
	else:
		return minr - 2 * 3

def getinput():

	def getint():
		return int(input())

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

	def getints(n):
		return [getint() for _ in range(n)]

	def getints_lines(n):
		return [getints_line() for _ in range(n)]
	(n, m) = getints_line()
	return [n, m, getints_lines(m)]

def iosolve():
	return str(solve(*getinput()))

def main():
	if sys.stdin.isatty():
		test()
	stdin_lines = getstdin_lines()
	sys.stdin = io.StringIO('\n'.join(stdin_lines))
	if stdin_lines:
		print(iosolve())
	else:
		test()

def test():
	IO_TEST_CASES = [('5 6\n1 2\n1 3\n2 3\n2 4\n3 4\n4 5\n            ', '2\n            '), ('7 4\n2 1\n3 6\n5 1\n1 7\n            ', '-1\n            ')]
	TEST_CASES = []
	import unittest
	import sys
	import io

	class Assert(unittest.TestCase):

		def equal(self, a, b):
			self.assertEqual(a, b)

		def float_equal(self, actual, expect, tolerance):
			self.assertTrue(expect - tolerance < actual < expect + tolerance)
	art = Assert()
	for (inputs, expect) in TEST_CASES:
		art.equal(solve(*inputs), expect)
	for (stdin, expect) in IO_TEST_CASES:
		sys.stdin = io.StringIO(stdin.strip())
		art.equal(iosolve(), expect.strip())

def getstdin_lines():
	stdin = []
	while 1:
		try:
			stdin.append(input())
		except EOFError:
			break
	return stdin

def __starting_point():
	main()
__starting_point()


import itertools as it
import collections as cc
import heapq as hp
import sys
import collections as cc
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, m) = I()
edg = []
g = [[0] * n for i in range(n)]
deg = [0] * n
for i in range(m):
	(x, y) = I()
	x -= 1
	y -= 1
	edg.append([x, y])
	g[x][y] = 1
	g[y][x] = 1
	deg[x] += 1
	deg[y] += 1
ans = 10 ** 9 + 7
tf = 0
for i in edg:
	(x, y) = i
	for j in range(n):
		if g[x][j] and g[y][j]:
			temp = deg[x] + deg[y] + deg[j] - 6
			ans = min(ans, temp)
			tf = 1
if tf:
	print(ans)
else:
	print(-1)


(n, m) = list(map(int, input().split()))
neighboor = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	neighboor[a].append(b)
	neighboor[b].append(a)
minimum = float('inf')

def rec(a, b=None, c=None):
	r1 = len(neighboor[a]) - 2
	r2 = len(neighboor[b]) - 2 if b else 0
	r3 = len(neighboor[c]) - 2 if c else 0
	return r1 + r2 + r3
for i in range(1, n + 1):
	if rec(i) < 0:
		continue
	for j in neighboor[i]:
		if rec(j) < 0:
			continue
		for k in neighboor[j]:
			if k in neighboor[i]:
				r = rec(i, j, k)
				minimum = r if r < minimum else minimum
print(minimum if minimum != float('inf') else -1)


(n, m) = map(int, input().split())
Set = [set() for i in range(n)]
edges = []
for i in range(m):
	a = tuple(map(int, input().split()))
	a = (a[0] - 1, a[1] - 1)
	edges.append(a)
	Set[a[0]].add(a[1])
	Set[a[1]].add(a[0])
lens = [0] * n
for i in range(n):
	lens[i] = len(Set[i])
mini = 1000000
for i in range(m):
	a = edges[i][0]
	b = edges[i][1]
	inter = Set[a] & Set[b]
	for elem in inter:
		mini = min(mini, lens[a] + lens[b] + lens[elem] - 6)
if mini == 1000000:
	print('-1')
else:
	print(mini)


def main():
	from itertools import combinations
	(n, m) = map(int, input().split())
	n += 1
	(l, cnt, res) = ([[] for _ in range(n)], [0] * n, [])
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a < b:
			l[a].append(b)
		else:
			l[b].append(a)
		cnt[a] += 1
		cnt[b] += 1
	for (a, la, x) in zip(range(n), l, cnt):
		la.sort()
		for (b, c) in combinations(la, 2):
			if c in l[b]:
				res.append(x + cnt[b] + cnt[c])
	print(min(res) - 6 if res else -1)
main()


(n, m) = map(int, input().split())
MAX = 4107
recognition = [0] * MAX
t = [[False] * MAX for i in range(MAX)]
for i in range(m):
	(a, b) = map(int, input().split())
	t[a][b] = True
	t[b][a] = True
	recognition[a] += 1
	recognition[b] += 1
result = int(1000000000.0)
for a in range(1, n + 1):
	for b in range(a + 1, n + 1):
		if t[a][b]:
			for c in range(b + 1, n + 1):
				if t[a][c] and t[b][c]:
					result = min(result, recognition[a] + recognition[b] + recognition[c] - 6)
if result == int(1000000000.0):
	print('-1')
else:
	print(result)


(n, m) = map(int, input().split())
adj = [0] * n
for i in range(n):
	adj[i] = []
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
res = int(1000000.0)
for i in range(n):
	curr = set(adj[i])
	for j in adj[i]:
		for k in adj[j]:
			if k in curr:
				res = min(res, len(adj[i]) + len(adj[j]) + len(adj[k]) - 6)
print(-1 if res == int(1000000.0) else res)


(a, b) = map(int, input().split())
c = [[] for i in range(a)]
for i in range(b):
	(first, second) = map(int, input().split())
	c[first - 1].append(second - 1)
	c[second - 1].append(first - 1)
res = 100000
for i in range(a):
	current = set(c[i])
	for j in c[i]:
		for k in c[j]:
			if k in current:
				res = min(res, len(c[i]) + len(c[j]) + len(c[k]) - 6)
print(-1 if res == 100000 else res)


(n, m) = map(int, input().split())
g = [set() for i in range(n)]
for _ in range(m):
	(i, j) = map(int, input().split())
	g[i - 1].add(j - 1)
	g[j - 1].add(i - 1)
m = float('inf')
for i in range(len(g) - 1):
	wi = len(g[i])
	for j in range(1, len(g)):
		wj = len(g[j])
		if i in g[j] and j in g[i]:
			rs = list(map(lambda x: len(g[x]), g[i].intersection(g[j])))
			if len(rs) > 0:
				m = min(m, min(rs) + wi + wj)
print(m - 6 if m != float('inf') else -1)


class CodeforcesTask574BSolution:

	def __init__(self):
		self.result = ''
		self.n_m = []
		self.connections = []

	def read_input(self):
		self.n_m = [int(x) for x in input().split(' ')]
		for x in range(self.n_m[1]):
			self.connections.append([int(y) for y in input().split(' ')])

	def process_task(self):
		graph = [set() for x in range(self.n_m[0])]
		for conn in self.connections:
			graph[conn[0] - 1].add(conn[1])
			graph[conn[1] - 1].add(conn[0])
		mn = self.n_m[0] ** 2
		found = False
		for first in range(self.n_m[0]):
			for second in list(graph[first - 1]):
				for third in list(graph[first - 1]):
					if second != third and third in graph[second - 1]:
						found = True
						mn = min(mn, len(graph[first - 1]) + len(graph[second - 1]) + len(graph[third - 1]) - 6)
		self.result = '-1' if not found else str(mn)

	def get_result(self):
		return self.result
Solution = CodeforcesTask574BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


(n, m) = map(int, input().split())
graph = [set() for i in range(n)]
edges = []
start = 10 ** 10000
result = start
for i in range(m):
	a = tuple(map(int, input().split()))
	a = (a[0] - 1, a[1] - 1)
	edges.append(a)
	graph[a[0]].add(a[1])
	graph[a[1]].add(a[0])
lens = [0] * n
for i in range(n):
	lens[i] = len(graph[i])
for i in range(m):
	x = edges[i][0]
	y = edges[i][1]
	inter = graph[x] & graph[y]
	for elem in inter:
		result = min(result, lens[x] + lens[y] + lens[elem] - 6)
if result == start:
	print(-1)
else:
	print(result)


(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
answer = 99999999
for i in range(n):
	if len(graph[i]) < 2:
		continue
	for j in range(len(graph[i])):
		for k in range(j + 1, len(graph[i])):
			(a, b, c) = (i, graph[i][j], graph[i][k])
			if graph[b].count(c):
				answer = min(answer, len(graph[a]) + len(graph[b]) + len(graph[c]) - 6)
if answer != 99999999:
	print(answer)
else:
	print(-1)


def main():
	import sys
	tokens = [int(i) for i in sys.stdin.read().split()]
	tokens.reverse()
	(n, m) = (tokens.pop(), tokens.pop())
	degree = [0] * n
	edges = [None] * m
	graph = [set() for i in range(n)]
	for i in range(m):
		(a, b) = (tokens.pop() - 1, tokens.pop() - 1)
		degree[a] += 1
		degree[b] += 1
		edges[i] = (a, b)
		graph[a].add(b)
		graph[b].add(a)
	result = 10 ** 9
	for (a, b) in edges:
		if degree[a] < degree[b]:
			(a, b) = (b, a)
		for c in graph[a]:
			if c in graph[b]:
				result = min(result, degree[a] + degree[b] + degree[c])
	if result == 10 ** 9:
		print(-1)
	else:
		print(result - 6)
main()


(n, m) = [int(i) for i in input().split()]
l = [[0 for j in range(n)] for i in range(n)]
adj = [[] for i in range(n)]
out = [0 for i in range(n)]
for i in range(m):
	(a, b) = [int(i) - 1 for i in input().split()]
	out[a] += 1
	out[b] += 1
	l[a][b] = 1
	l[b][a] = 1
	adj[a].append(b)
	adj[b].append(a)
ans = 10000000000000
for i in range(n):
	if out[i] >= 2:
		for f in range(len(adj[i])):
			if out[adj[i][f]] >= 2:
				for sx in range(f + 1, len(adj[i])):
					if out[adj[i][sx]] >= 2:
						if l[adj[i][f]][adj[i][sx]] == 1:
							ans = min(ans, out[i] - 2 + out[adj[i][f]] - 2 + out[adj[i][sx]] - 2)
if ans == 10000000000000:
	print(-1)
else:
	print(ans)


from collections import defaultdict, deque

def main():
	(n, m) = map(int, input().split())
	d = defaultdict(set)
	for i in range(m):
		(a, b) = map(int, input().split())
		d[a].add(b)
		d[b].add(a)
	ans = 10000000000.0
	for (key, v) in d.items():
		for j in v:
			for k in v:
				if k in d[j]:
					ans = min(ans, len(v) + len(d[j]) + len(d[k]) - 6)
	print(ans if ans != 10000000000.0 else '-1')
main()


import os, sys, math
from io import BytesIO, IOBase
from collections import defaultdict, deque, OrderedDict
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

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

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

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

def Sn():
	return input().strip()
BUFSIZE = 8192

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

def solve():
	(n, k) = In()
	d = defaultdict(set)
	for i in range(k):
		(a, b) = In()
		d[a].add(b)
		d[b].add(a)
	ans = P
	for i in range(1, n + 1):
		if len(d[i]) < 2:
			continue
		l = []
		for x in d[i]:
			if len(d[x]) >= 2:
				l.append((x, len(d[x])))
		l.sort(key=lambda x: x[1])
		l.insert(0, (i, len(d[i])))
		n1 = len(l)
		for j1 in range(n1):
			for j2 in range(j1 + 1, n1):
				if l[j1][0] in d[i] and l[j2][0] in d[i] and (l[j1][0] in d[l[j2][0]]):
					t = len(d[i]) - 2 + l[j1][1] - 2 + l[j2][1] - 2
					ans = min(ans, t)
	if ans == P:
		ans = -1
	print(ans)
	pass

def main():
	T = 1
	for i in range(T):
		solve()
M = 998244353
P = 1000000007

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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


II = lambda : map(int, input().split())
(n, m) = II()
from collections import defaultdict
edges = defaultdict(set)
for _ in range(m):
	(a, b) = II()
	edges[a].add(b)
	edges[b].add(a)
ans = 99999999
for v in edges.values():
	for second in v:
		for third in v:
			if third in edges[second]:
				reg = len(edges[third]) + len(edges[second]) + len(v) - 6
				if reg >= 0:
					ans = min(ans, reg)
print(ans if ans != 99999999 else -1)


(n, m) = map(int, input().split())
listaAdj = [[] for j in range(n)]
soma = float('inf')
for i in range(m):
	(a, b) = map(int, input().split())
	listaAdj[a - 1].append(b - 1)
	listaAdj[b - 1].append(a - 1)
total = [len(listaAdj[i]) for i in range(n)]
for i in range(n):
	for j in listaAdj[i]:
		for k in set(listaAdj[i]).intersection(set(listaAdj[j])):
			soma = min(soma, total[i] + total[j] + total[k] - 6)
if soma == float('inf'):
	print(-1)
else:
	print(soma)


w = input().split(' ')
n = int(w[0])
m = int(w[1])
arr = []
for i in range(n):
	arr.append([])
edges = []
for i in range(m):
	w = input().split(' ')
	a = int(w[0])
	b = int(w[1])
	arr[a - 1].append(b - 1)
	arr[b - 1].append(a - 1)
	edges.append([a - 1, b - 1])
mn = 12000
for edge in edges:
	a = len(arr[edge[0]])
	b = len(arr[edge[1]])
	if a > 1 and b > 1:
		sm = a + b - 4
		for i in arr[edge[0]]:
			if i in arr[edge[1]]:
				mn = min(mn, sm - 2 + len(arr[i]))
if mn == 12000:
	print('-1')
else:
	print(mn)


(n, m) = map(int, input().split())
Es = [set() for i in range(n)]
edges = set()
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	Es[a].add(b)
	Es[b].add(a)
	edges.add((a, b))
record = float('inf')
for (a, b) in edges:
	cost_a = len(Es[a]) - 2
	cost_b = len(Es[b]) - 2
	cost = cost_a + cost_b
	if cost >= record:
		continue
	if cost_a > cost_b:
		(a, b) = (b, a)
	for c in Es[a]:
		cost_abc = cost + len(Es[c]) - 2
		if b in Es[c]:
			if cost_abc < record:
				record = cost_abc
if record == float('inf'):
	print(-1)
else:
	print(record)


def main():
	M = int(1000000000000.0)
	(n, m) = map(int, input().split())
	graph = [set() for _ in range(n + 1)]
	edges = []
	for _ in range(m):
		(a, b) = map(int, input().split())
		edges += [(a, b)]
		graph[a] |= {b}
		graph[b] |= {a}
	res = M
	for (a, b) in edges:
		for common in graph[a] & graph[b]:
			res = min(res, len(graph[a]) + len(graph[b]) + len(graph[common]) - 6)
	print(res if res < M else -1)
main()


from collections import Counter as cntr
from math import inf

def cin():
	return map(int, input().split(' '))
(n, m) = cin()
p = []
s = [set() for i in range(n + 1)]
h = [0 for i in range(n + 1)]
for i in range(m):
	(a, b) = cin()
	p += [(a, b, c) for c in s[a].intersection(s[b])]
	s[a].add(b)
	s[b].add(a)
	h[a] += 1
	h[b] += 1
print(min((h[a] + h[b] + h[c] for (a, b, c) in p)) - 6 if p else -1)


(n, m) = [int(x) for x in input().split()]
edges = [[False] * (n + 1) for i in range(n + 1)]
kn = [0] * (n + 1)
d = dict()
for i in range(1, n + 1):
	d[i] = []
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	edges[min(a, b)][max(a, b)] = True
	d[min(a, b)].append(max(a, b))
	kn[a] += 1
	kn[b] += 1
ans = 10 ** 6
for i in range(1, n - 1):
	for j in d[i]:
		for k in d[j]:
			if edges[i][k]:
				ans = min(ans, kn[i] + kn[j] + kn[k])
if ans == 10 ** 6:
	print(-1)
else:
	print(ans - 6)


import unittest
import sys

class Musk:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		(self.n, self.m) = list(map(int, uinput().split()))
		pairs = ' '.join((uinput() for i in range(self.m))).split()
		self.numa = [int(pairs[i]) - 1 for i in range(0, 2 * self.m, 2)]
		self.numb = [int(pairs[i]) - 1 for i in range(1, 2 * self.m, 2)]
		self.sets = [set() for i in range(self.n)]
		for i in range(self.m):
			self.sets[self.numa[i]].add(self.numb[i])
			self.sets[self.numb[i]].add(self.numa[i])
		MAX = 10000000000000000
		self.min_rank = MAX
		for i in range(self.n):
			for j in self.sets[i]:
				if j > i:
					un = len(self.sets[i]) + len(self.sets[j])
					intersect = self.sets[i].intersection(self.sets[j])
					for s in intersect:
						uns = un + len(self.sets[s])
						rank = uns - 6
						if rank < self.min_rank:
							self.min_rank = rank
		if self.min_rank == MAX:
			self.min_rank = -1

	def calculate(self):
		result = self.min_rank
		return str(result)

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '5 6\n1 2\n1 3\n2 3\n2 4\n3 4\n4 5'
		d = Musk(test)
		self.assertEqual(d.n, 5)
		self.assertEqual(d.m, 6)
		self.assertEqual(d.numa, [0, 0, 1, 1, 2, 3])
		self.assertEqual(d.numb, [1, 2, 2, 3, 3, 4])
		self.assertEqual(d.sets[0], {1, 2})
		self.assertEqual(d.sets[3], {1, 2, 4})
		self.assertEqual(Musk(test).calculate(), '2')
		test = '7 4\n2 1\n3 6\n5 1\n1 7'
		self.assertEqual(Musk(test).calculate(), '-1')
		test = '1\n1 2\n1'
		test = '1\n1 2\n1'

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Musk(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))

def __starting_point():
	sys.setrecursionlimit(100000)
	if sys.argv[-1] == '-ut':
		unittest.main(argv=[' '])
	sys.stdout.write(Musk().calculate())
__starting_point()


def main():
	(n, m) = map(int, input().split())
	n += 1
	(vv, ee, cnt, res) = ([set() for _ in range(n)], [], [0] * n, [])
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a < b:
			vv[a].add(b)
		else:
			vv[b].add(a)
		cnt[a] += 1
		cnt[b] += 1
		ee.append((a, b))
	for (a, b) in ee:
		x = cnt[a] + cnt[b]
		for c in vv[a].intersection(vv[b]):
			res.append(x + cnt[c])
	print(min(res) - 6 if res else -1)
main()


(n, m) = map(int, input().split())
edge = []
adjacent_vertex = [set() for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	edge += [(u, v)]
	adjacent_vertex[u] |= {v}
	adjacent_vertex[v] |= {u}
k = [len(adjacent_vertex[i]) for i in range(n + 1)]
result = -1
for (u, v) in edge:
	w = adjacent_vertex[u] & adjacent_vertex[v]
	for i in w:
		recognition = k[u] + k[v] + k[i] - 6
		if result == -1 or result > recognition >= 0:
			result = recognition
print(result)


from collections import *

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input())
(n, m) = li()
d = defaultdict(set)
l = [0] * n
for i in range(m):
	(a, b) = li()
	d[a].add(b)
	d[b].add(a)
	l[a - 1] += 1
	l[b - 1] += 1
for i in d:
	d[i] = sorted(list(d[i]), key=lambda x: l[x - 1])
ans = 100000000000000000000000000
for i in sorted(list(d), key=lambda x: l[x - 1]):
	for j in d[i]:
		for k in d[j]:
			if k not in d[i]:
				continue
			else:
				ans = min(ans, l[i - 1] + l[j - 1] + l[k - 1])
				break
print(ans - 6 if ans != 100000000000000000000000000 else -1)


(n, m) = map(int, input().split())
zn_kol = [0] * n
zn = [[] for i in range(n)]
zn_edge = [set() for i in range(n)]
ans = 100000000
for i in range(m):
	(a, b) = map(int, input().split())
	zn_kol[a - 1] += 1
	zn_kol[b - 1] += 1
	zn_edge[a - 1].add(b - 1)
	zn_edge[b - 1].add(a - 1)
	zn[b - 1].append(a - 1)
	zn[a - 1].append(b - 1)
for i in range(n):
	for j in range(zn_kol[i] - 1):
		for z in range(j + 1, zn_kol[i]):
			if zn[i][j] in zn_edge[zn[i][z]]:
				if zn_kol[zn[i][j]] - 2 + zn_kol[zn[i][z]] - 2 + zn_kol[i] - 2 < ans:
					ans = zn_kol[zn[i][j]] - 2 + zn_kol[zn[i][z]] - 2 + zn_kol[i] - 2
if ans == 100000000:
	print(-1)
else:
	print(ans)


def search_cicles(graph):
	ciclos = []
	for v1 in graph:
		for v2 in graph[v1]:
			for j1 in graph[v2]:
				if j1 in graph[v1]:
					ciclos.append((v1, v2, j1))
	return ciclos

def chooses_musketeers(graph):
	ciclos = search_cicles(graph)
	if len(ciclos) == 0:
		return -1
	samller = 10 ** 5
	for cycle in ciclos:
		total = 0
		for v in cycle:
			result = len(graph[v]) - 2
			total += result
		if total < samller:
			samller = total
	return samller
(n, m) = map(int, input().split())
graph = {}
for i in range(1, n + 1):
	graph[i] = []
for i in range(m):
	(origin, destiny) = map(int, input().split())
	graph[origin].append(destiny)
	graph[destiny].append(origin)
print(chooses_musketeers(graph))


(n, m) = map(int, input().split())
edge = []
arr = [set() for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	edge.append((u, v))
	arr[u].add(v)
	arr[v].add(u)
ret = 1e+19
for (u, v) in edge:
	tmp = arr[u] & arr[v]
	for h in tmp:
		if h in arr[u] and h in arr[v]:
			ret = min(ret, len(arr[h]) + len(arr[v]) + len(arr[u]) - 6)
if ret == 1e+19:
	ret = -1
print(ret)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
adj = [[0] * 4001 for i in range(4001)]
recog = 10 ** 18
deg = [0] * 4001
for i in range(m):
	(a, b) = map(int, input().split())
	adj[a][b] = 1
	adj[b][a] = 1
	deg[a] += 1
	deg[b] += 1
for i in range(1, 1 + n):
	for j in range(i + 1, 1 + n):
		if adj[i][j]:
			for k in range(j + 1, n + 1):
				if adj[i][k] and adj[j][k]:
					recog = min(recog, deg[i] + deg[j] + deg[k])
print(recog - 6 if recog != 10 ** 18 else -1)


from sys import stdin
(nV, nE) = map(int, stdin.readline().split())
adj = [[0 for _ in range(nV + 1)] for _ in range(nV + 1)]
d = [0] * (nV + 1)
edges = []
for _ in range(nE):
	(u, v) = map(int, stdin.readline().split())
	adj[u][v] = adj[v][u] = 1
	d[u] += 1
	d[v] += 1
	edges.append((u, v))
ret = float('inf')
for (a, b) in edges:
	for c in range(1, nV + 1):
		if adj[a][b] and adj[a][c] and adj[b][c]:
			ret = min(ret, d[a] + d[b] + d[c] - 6)
print(ret if ret != float('inf') else -1)


s = input().split()
n = int(s[0])
m = int(s[1])
graph = [[0 for x in range(n + 1)] for x in range(n + 1)]
_graph = [[] for x in range(n + 1)]
degree = [0 for x in range(n + 1)]
min = n + n + n + 1
for item in range(m):
	s = input().split()
	i = int(s[0])
	j = int(s[1])
	_graph[i].append(j)
	_graph[j].append(i)
	graph[i][j] = 1
	graph[j][i] = 1
	degree[i] += 1
	degree[j] += 1
for i in range(1, n):
	for item in _graph[i]:
		for k in range(n):
			if graph[i][k] == 1 and graph[item][k] == 1:
				key = degree[i] + degree[item] + degree[k]
				if key < min:
					min = key
if min == n + n + n + 1:
	print(-1)
else:
	print(min - 6)


(n, m) = map(int, input().split())
aux = [0] * (n + 1)
for i in range(n + 1):
	aux[i] = []
for i in range(m):
	(u, v) = map(int, input().split())
	aux[u].append(v)
	aux[v].append(u)
ans = 4000
for i in range(1, n + 1):
	distinct = set(aux[i])
	for j in aux[i]:
		for k in aux[j]:
			if k in distinct:
				ans = min(ans, len(aux[i]) + len(aux[j]) + len(aux[k]) - 6)
print(ans if ans != 4000 else -1)


M = int(1000000000000.0)
(n, m) = map(int, input().split())
g = [set() for _ in range(n + 1)]
e = []
for _ in range(m):
	(a, b) = map(int, input().split())
	e += [(a, b)]
	g[a] |= {b}
	g[b] |= {a}
ans = M
for (a, b) in e:
	for i in g[a] & g[b]:
		ans = min(ans, len(g[a]) + len(g[b]) + len(g[i]) - 6)
print(ans if ans < M else -1)


(n, m) = map(int, input().split())
p = []
s = [set() for _ in range(n + 1)]
h = [0] * (n + 1)
for _ in range(m):
	(a, b) = map(int, input().split())
	p += [(a, b, c) for c in s[a].intersection(s[b])]
	s[a].add(b)
	s[b].add(a)
	h[a] += 1
	h[b] += 1
print(min((h[a] + h[b] + h[c] for (a, b, c) in p)) - 6 if p else -1)


import sys
lines = sys.stdin.read().split('\n')
(n, m) = map(int, lines[0].split(' '))
gra1 = []
for i in range(n + 1):
	gra1.append(set())
gra2 = [0] * (n + 1)
edges = []
for i in range(1, m + 1):
	(a, b) = map(int, lines[i].split(' '))
	gra1[a].add(b)
	gra1[b].add(a)
	edges.append((a, b))
for i in range(1, n + 1):
	gra2[i] = len(gra1[i])
res = []
for edge in edges:
	(a, b) = edge
	tmp = gra2[a] + gra2[b]
	neighs = gra1[a].intersection(gra1[b])
	if len(neighs) <= 0:
		continue
	best = float('inf')
	for c in list(neighs):
		if gra2[c] < best:
			best = gra2[c]
	res.append(tmp + best)
res.sort()
if len(res) <= 0:
	print('-1')
else:
	print(res[0] - 6)


(n, m) = list(map(int, input().split()))
d2 = []
od = []
edges = []
for i in range(n):
	d2.append(set())
	od.append(0)
for i in range(m):
	(a, b) = list(map(int, input().split()))
	edges.append((a - 1, b - 1))
	d2[a - 1].add(b - 1)
	d2[b - 1].add(a - 1)
	od[a - 1] += 1
	od[b - 1] += 1
minsum = 1000000
for edg in edges:
	(a, b) = edg
	nerd = d2[a] & d2[b]
	for c in nerd:
		tmpsum = od[a] + od[b] + od[c] - 6
		if tmpsum < minsum:
			minsum = tmpsum
if minsum == 1000000:
	print('-1')
else:
	print(minsum)


from collections import deque, defaultdict
(n, m) = map(int, input().split())
g = defaultdict(list)
for i in range(m):
	(x, y) = map(int, input().split())
	g[x].append(y)
	g[y].append(x)
v = []
res = 10 ** 6 + 1
for i in range(1, n + 1):
	curr = g[i]
	for j in g[i]:
		for k in g[j]:
			if k in curr:
				res = min(res, len(g[i]) + len(g[j]) + len(g[k]) - 6)
if res == 10 ** 6 + 1:
	print('-1')
else:
	print(res)


def build_graph(arr, largest):
	result = [[] for j in range(largest)]
	for (a, b) in arr:
		result[a - 1].append(b - 1)
		result[b - 1].append(a - 1)
	return result

def solve(graph):
	minimum = -1
	for w in range(len(graph)):
		for f in graph[w]:
			for ff in graph[f]:
				if w in graph[ff]:
					friendSum = len(graph[w]) + len(graph[f]) + len(graph[ff]) - 6
					if minimum == -1 or friendSum < minimum:
						minimum = friendSum
	return minimum
(n, m) = map(int, input().split())
inputs = []
largest = 0
for _ in range(m):
	(a, b) = map(int, input().split())
	inputs.append((a, b))
	largest = max(largest, a, b)
graph = build_graph(inputs, largest)
print(solve(graph))


from sys import stdin
(n, m) = map(int, input().split())
degree = [0] * (n + 1)
knows = [[False] * (n + 1) for i in range(n + 1)]
for i in range(m):
	(a, b) = stdin.readline().split()
	a = int(a)
	b = int(b)
	knows[a][b] = knows[b][a] = True
	degree[a] += 1
	degree[b] += 1
deg = 1000000
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if knows[i][j]:
			for k in range(j + 1, n + 1):
				if knows[i][k] and knows[j][k]:
					sum_degree = degree[i] + degree[j] + degree[k]
					if sum_degree < deg:
						deg = sum_degree
if deg == 1000000:
	print(-1)
else:
	print(deg - 6)


(n, m) = map(int, input().split())
t = m
grafo = [[] for i in range(n + 1)]
while t > 0:
	(ai, bi) = map(int, input().split())
	grafo[ai].append(bi)
	grafo[bi].append(ai)
	t -= 1
minimo = n * 3
for i in range(1, n - 1):
	if len(grafo[i]) < 2:
		continue
	else:
		for j in grafo[i]:
			if len(grafo[j]) < 2:
				continue
			else:
				for k in grafo[j]:
					if k in grafo[i]:
						aux = len(grafo[i]) + len(grafo[j]) + len(grafo[k]) - 6
						if aux < minimo:
							minimo = aux
if minimo < n * 3:
	print(minimo)
else:
	print(-1)


(n, m) = map(int, input().split())
a = [[False] * n for _ in range(n)]
edges = []
d = [0] * n
for i in range(m):
	(u, v) = map(int, input().split())
	a[u - 1][v - 1] = a[v - 1][u - 1] = True
	edges.append((u - 1, v - 1))
	d[u - 1] += 1
	d[v - 1] += 1
ans = int(10000000000.0)
for i in range(m):
	(u, v) = (edges[i][0], edges[i][1])
	for j in range(n):
		if a[u][j] and a[v][j] and (u != j) and (v != j):
			ans = min(ans, d[u] + d[v] + d[j] - 6)
print(-1 if ans == int(10000000000.0) else ans)


from collections import defaultdict
MAX = float('inf')

def minimal_recognitions(graph):
	sum_recognitions = MAX
	for n1 in graph:
		for n2 in graph[n1]:
			for n3 in graph[n2]:
				if n3 in graph[n1]:
					sum_recognitions = min(sum_recognitions, len(graph[n3]) + len(graph[n2]) + len(graph[n1]))
	return sum_recognitions
(n, m) = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
	(x1, x2) = map(int, input().split())
	graph[x1].append(x2)
	graph[x2].append(x1)
minimal_sum_recognitions = minimal_recognitions(graph)
if minimal_sum_recognitions == MAX:
	print(-1)
else:
	print(minimal_sum_recognitions - 6)


(n, m) = map(int, input().split())
L = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	L[a].append(b)
	L[b].append(a)
mi = 9999999999999
for i in range(1, n + 1):
	for x in L[i]:
		for y in L[x]:
			if i in L[y]:
				mi = min(mi, len(L[i]) + len(L[x]) + len(L[y]) - 6)
if mi != 9999999999999:
	print(mi)
else:
	print(-1)


arestas = []
init = 10 ** 10000
resultado = init
(n, m) = map(int, input().split())
grafo = [set() for _ in range(n)]
for _ in range(m):
	warriors = tuple(map(int, input().split()))
	warriors = (warriors[0] - 1, warriors[1] - 1)
	arestas.append(warriors)
	grafo[warriors[0]].add(warriors[1])
	grafo[warriors[1]].add(warriors[0])
arr = [0] * n
for i in range(n):
	arr[i] = len(grafo[i])
for i in range(m):
	x = arestas[i][0]
	y = arestas[i][1]
	intersec = grafo[x] & grafo[y]
	for elem in intersec:
		resultado = min(resultado, arr[x] + arr[y] + arr[elem] - 6)
if resultado != init:
	print(resultado)
else:
	print(-1)


(n, m) = [int(x) for x in input().split()]
guerreiros = [[False] * n for _ in range(n)]
grau = [0] * n
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	guerreiros[a - 1][b - 1] = True
	guerreiros[b - 1][a - 1] = True
	grau[a - 1] += 1
	grau[b - 1] += 1
resultado = 100000000000
for i in range(n):
	for j in range(i + 1, n):
		if guerreiros[i][j]:
			for k in range(j + 1, n):
				if guerreiros[i][k] and guerreiros[j][k]:
					soma = grau[i] + grau[j] + grau[k]
					resultado = min(resultado, soma)
print('-1' if resultado == 100000000000 else resultado - 6)


def bearAndThreeMustketeers(n, m, grafo):
	aux = m
	while aux > 0:
		(entradaA, entradaB) = map(int, input().split())
		grafo[entradaA].append(entradaB)
		grafo[entradaB].append(entradaA)
		aux -= 1
	resposta = n * 3
	for i in range(1, n + 1):
		for j in range(len(grafo[i])):
			for k in range(j + 1, len(grafo[i])):
				if grafo[i][j] in grafo[grafo[i][k]]:
					resposta = min(resposta, len(grafo[i]) + len(grafo[grafo[i][j]]) + len(grafo[grafo[i][k]]) - 6)
	if resposta < n * 3:
		print(resposta)
	else:
		print(-1)
(n, m) = map(int, input().split())
grafo = [list() for _ in range(n + 1)]
bearAndThreeMustketeers(n, m, grafo)


minimo = 1000000000000
inf = minimo

def fill_list(limit):
	lista = []
	for i in range(limit):
		lista.append([0, 0])
	return lista

def fill_matrix(limit):
	matrix = []
	for i in range(limit):
		line = []
		for j in range(limit):
			line.append(0)
		matrix.append(line)
	return matrix

def fill_dic(key):
	if key in dic_roads:
		dic_roads[key] += 1
	else:
		dic_roads[key] = 1
entrada = input().split()
n = int(entrada[0])
m = int(entrada[1])
pares = fill_list(m)
adj_matrix = fill_matrix(n)
dic_roads = {}
for i in range(m):
	values = input().split()
	u = int(values[0])
	v = int(values[1])
	pares[i][0] = u
	pares[i][1] = v
	u -= 1
	v -= 1
	fill_dic(u)
	fill_dic(v)
	adj_matrix[u][v] = 1
	adj_matrix[v][u] = 1
for i in range(m):
	u = pares[i][0] - 1
	v = pares[i][1] - 1
	for j in range(n):
		if adj_matrix[u][j] == 1 and adj_matrix[v][j] == 1:
			total = dic_roads[u] + dic_roads[v] + dic_roads[j] - 6
			if total < minimo:
				minimo = total
if minimo == inf:
	print(-1)
else:
	print(minimo)


import sys
sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, m) = I()
g = [[0] * n for i in range(n)]
ed = []
an = n * n
dg = [0] * n
for i in range(m):
	(x, y) = I()
	x -= 1
	y -= 1
	dg[x] += 1
	dg[y] += 1
	g[x][y] = 1
	g[y][x] = 1
	ed.append([x, y])
for i in range(m):
	(a, b) = ed[i]
	for j in range(n):
		if j != a and j != b and g[a][j] and g[j][b]:
			an = min(an, dg[a] + dg[b] + dg[j] - 6)
if an == n * n:
	an = -1
print(an)


import sys
(n, m) = map(int, input().split())
narr = dict()
freq = [0] * n
arestas = []
for _ in range(m):
	(w1, w2) = map(int, input().split())
	narr[w1] = narr.get(w1, []) + [w2]
	narr[w2] = narr.get(w2, []) + [w1]
	freq[w1 - 1] += 1
	freq[w2 - 1] += 1
	arestas.append([w1, w2])
for i in range(1, n + 1):
	if i not in narr:
		narr[i] = []
minReco = sys.maxsize
for aresta in range(len(arestas)):
	no1 = arestas[aresta][0]
	no2 = arestas[aresta][1]
	for node in range(1, n + 1):
		if node != no1 and node != no2:
			if no1 in narr[node] and no2 in narr[node]:
				recognitions = freq[no1 - 1] + freq[no2 - 1] + freq[node - 1] - 6
				if recognitions < minReco:
					minReco = recognitions
print('-1' if minReco == sys.maxsize else minReco)


import sys
from collections import defaultdict
(N, M) = input().split()
N = int(N)
M = int(M)
neighbours = defaultdict(set)
edges = set()
for _ in range(M):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	edges.add((a, b))
	neighbours[a].add(b)
	neighbours[b].add(a)
degree = {}
for node in neighbours:
	degree[node] = len(neighbours[node])
triplets = set()
for (a, b) in edges:
	mutual_neighbours = neighbours[a] & neighbours[b]
	if len(mutual_neighbours) == 0:
		continue
	best_mn = sorted(((degree[n], n) for n in mutual_neighbours))[0][1]
	triplets.add((a, b, best_mn))

def recognition(a, b, c):
	return degree[a] + degree[b] + degree[c] - 6
if len(triplets) == 0:
	print(-1)
else:
	mn_d = [recognition(*triplet) for triplet in triplets]
	print(min(mn_d))


(n, m) = map(int, input().split())
edge = []
conjunto = [set() for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	edge += [(u, v)]
	conjunto[u] |= {v}
	conjunto[v] |= {u}
k = [len(conjunto[i]) for i in range(n + 1)]
saida = -1
for (u, v) in edge:
	w = conjunto[u] & conjunto[v]
	for i in w:
		res = k[u] + k[v] + k[i] - 6
		if saida == -1 or saida > res >= 0:
			saida = res
print(saida)


(n, m) = map(int, input().split())
d = {key: set() for key in range(1, n + 1)}
for item in range(m):
	(first, second) = map(int, input().split())
	d[first].add(second)
	d[second].add(first)
minimum = 1234567890

def setLowest(path):
	global minimum
	minimum = min(minimum, len(d[path[0]]) + len(d[path[1]]) + len(d[path[2]]) - 6)

def findLowestValue(d, key, path, visited):
	path.append(key)
	for value in d[key]:
		if len(path) == 3:
			if path[0] in d[key]:
				setLowest(path)
			break
		elif value not in visited:
			visited.add(value)
			findLowestValue(d, value, path[:], set(visited))

def solve(d):
	for key in d:
		if len(d[key]) >= 2:
			findLowestValue(d, key, [], {key})
solve(d)
print([minimum, -1][minimum == 1234567890])


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, kw) = map(int, input().split())
d = dict()
l = [0] * n
w = [0] * kw
k = [0] * kw
for i in range(n):
	d.update({i + 1: set()})
t = 999999999999999999999999
for i in range(kw):
	(a, b) = map(int, input().split())
	w[i] = a
	k[i] = b
	l[a - 1] += 1
	l[b - 1] += 1
	d[a].add(b)
	d[b].add(a)
for i in range(kw):
	for j in range(n):
		if j + 1 == w[i] or j + 1 == k[i]:
			continue
		if j + 1 in d[w[i]] and j + 1 in d[k[i]]:
			ans = l[j] + l[w[i] - 1] + l[k[i] - 1] - 6
			t = min(t, ans)
if t == 999999999999999999999999:
	print(-1)
else:
	print(t)


import itertools
(n, m) = map(int, input().split(' '))
l = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = list(map(int, input().split(' ')))
	l[a].append(b)
	l[b].append(a)
result = 0
sum = 4000
for i in range(n):
	lis = []
	for s in l[i]:
		if s > i:
			lis.append(s)
	for enum in itertools.combinations(lis, 2):
		(x, y) = enum
		temp = len(l[i]) + len(l[x]) + len(l[y]) - 6
		if temp < sum and x in l[y]:
			sum = temp
if sum == 4000:
	result = -1
else:
	result = sum
print(result)


from collections import defaultdict
(n, m) = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
	(v1, v2) = map(int, input().split())
	graph[v1].append(v2)
	graph[v2].append(v1)
sum_recogs = float('inf')
for i in graph:
	for j in graph[i]:
		for k in graph[j]:
			if k in graph[i]:
				sum_recogs = min(sum_recogs, len(graph[i]) + len(graph[k]) + len(graph[j]))
if sum_recogs == float('inf'):
	print(-1)
else:
	print(sum_recogs - 6)


(V, E) = tuple((int(i) for i in input().split()))
adjList = [[] for i in range(V)]
degree = [0 for i in range(V)]
for i in range(E):
	(u, v) = tuple((int(i) for i in input().split()))
	u -= 1
	v -= 1
	adjList[u].append(v)
	adjList[v].append(u)
	degree[u] += 1
	degree[v] += 1
ans = -1
for i in range(V):
	if degree[i] < 2:
		continue
	for n in range(len(adjList[i])):
		v1 = adjList[i][n]
		for m in range(len(adjList[v1])):
			v2 = adjList[v1][m]
			if v2 == i:
				continue
			if not i in adjList[v2]:
				continue
			cost = max(degree[i] - 2, 0) + max(degree[v1] - 2, 0) + max(degree[v2] - 2, 0)
			if ans == -1 or ans > cost:
				ans = cost
print(ans)


firstLine = input().split(' ')
warriorsNum = int(firstLine[0])
relationsNum = int(firstLine[1])
warriors = []
relations = [0] * warriorsNum
for i in range(warriorsNum):
	warriors.append([False] * warriorsNum)
for i in range(relationsNum):
	line = input().split(' ')
	warrior1 = int(line[0]) - 1
	warrior2 = int(line[1]) - 1
	relations[warrior1] += 1
	relations[warrior2] += 1
	warriors[warrior1][warrior2] = True
	warriors[warrior2][warrior1] = True
result = -1
for i in range(warriorsNum):
	warriorRelations = relations[i]
	for j in range(i, warriorsNum):
		if warriors[i][j]:
			for k in range(warriorsNum):
				if warriors[k][i] and warriors[k][j]:
					recognitions = relations[i] + relations[j] + relations[k] - 6
					if result == -1 or recognitions < result:
						result = recognitions
print(result)


f = lambda : map(int, input().split())
(n, m) = f()
k = n + 1
s = set()
d = [[] for i in range(k)]
for j in range(m):
	(u, v) = f()
	if u > v:
		(u, v) = (v, u)
	s.add((u, v))
	d[u].append(v)
	d[v].append(u)
for t in d:
	t.sort()
p = [len(t) for t in d]
b = 3 * n
for x in range(k):
	for (i, u) in enumerate(d[x]):
		for v in d[x][i + 1:]:
			if (u, v) in s:
				a = p[u] + p[v] + p[x]
				if a < b:
					b = a
print(b - 6 if b < 3 * n else -1)


(n, m) = map(int, input().split())
grafo = [set() for i in range(n)]
arestas = []
minimo = 1000000
for i in range(m):
	a = tuple(map(int, input().split()))
	a = (a[0] - 1, a[1] - 1)
	arestas.append(a)
	grafo[a[0]].add(a[1])
	grafo[a[1]].add(a[0])
lens = [0] * n
for i in range(n):
	lens[i] = len(grafo[i])
for i in range(m):
	a = arestas[i][0]
	b = arestas[i][1]
	inter = grafo[a] & grafo[b]
	for elem in inter:
		minimo = min(minimo, lens[a] + lens[b] + lens[elem] - 6)
if minimo == 1000000:
	print(-1)
else:
	print(minimo)


import sys
(n, m) = map(int, input().split())
cnts = {i: [] for i in range(1, n + 1)}
for i in range(m):
	(a, b) = map(int, input().split())
	cnts[a].append(b)
	cnts[b].append(a)
final = sys.maxsize
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if i in cnts[j]:
			for k in range(j + 1, n + 1):
				if i in cnts[k] and j in cnts[k]:
					final = min(final, len(cnts[i]) + len(cnts[j]) + len(cnts[k]))
if final == sys.maxsize:
	print(-1)
else:
	print(final - 6)


(n, m) = map(int, input().split())
edges = [set() for i in range(n + 1)]
res = 10 ** 10
pairs = []
for i in range(m):
	(a, b) = map(int, input().split())
	edges[a] |= {b}
	edges[b] |= {a}
	pairs.append([a, b])
for pair in pairs:
	union = edges[pair[0]] & edges[pair[1]]
	a = pair[0]
	b = pair[1]
	for v in union:
		if a in edges[v] and b in edges[v]:
			res = min(len(edges[a]) + len(edges[b]) + len(edges[v]) - 6, res)
print(-1 if res == 10 ** 10 else res)


from collections import defaultdict
import sys
(n, m) = list(map(int, input().split()))
graph = defaultdict(list)
deg = {}
for i in range(m):
	(a, b) = list(map(int, input().split()))
	graph[a].append(b)
	graph[b].append(a)
for i in graph:
	deg[i] = len(graph[i])
ans = sys.maxsize
for i in graph:
	for j in graph[i]:
		for k in graph[j]:
			if i in graph[k]:
				ans = min(ans, deg[i] + deg[j] + deg[k] - 6)
if sys.maxsize == ans:
	ans = -1
	print(ans)
else:
	print(ans)


(n, m) = [int(x) for x in input().split()]
adj = [set() for i in range(n + 1)]
degree = [0 for i in range(n + 1)]
answer = 999999
edges = []
for i in range(m):
	(u, v) = [int(x) for x in input().split()]
	edges.append((u, v))
	adj[u].add(v)
	degree[u] += 1
	adj[v].add(u)
	degree[v] += 1
for e in edges:
	for w in adj[e[0]]:
		if w in adj[e[1]]:
			answer = min(answer, degree[w] + degree[e[0]] + degree[e[1]] - 6)
if answer == 999999:
	print(-1)
else:
	print(answer)


__author__ = 'JohnHook'
(n, m) = list(map(int, input().split()))
graph = []
for i in range(n):
	graph.append([])
used = [False] * n
for i in range(m):
	temp = list(map(int, input().split()))
	graph[temp[0] - 1].append(temp[1] - 1)
	graph[temp[1] - 1].append(temp[0] - 1)
mn = float('Inf')

def rec(v):
	for i in graph[v]:
		if not used[i]:
			for j in graph[i]:
				if not used[j]:
					if j in graph[i] and j in graph[v]:
						global mn
						mn = min(mn, len(graph[v]) + len(graph[i]) + len(graph[j]) - 6)
	used[v] = True
for i in range(n):
	rec(i)
print(mn if mn != float('Inf') else -1)


(n, m) = map(int, input().split())
amatr = [[0] * n for i in range(n)]
alist = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	amatr[a - 1][b - 1] = 1
	amatr[b - 1][a - 1] = 1
	alist[a - 1].append(b - 1)
	alist[b - 1].append(a - 1)
known = [len(alist[i]) for i in range(n)]
ans = 10 ** 10
for first in range(n):
	for second in alist[first]:
		if amatr[first][second] == 1:
			for third in alist[second]:
				if amatr[third][second] == 1:
					if amatr[first][third] == 1:
						ans = min(ans, known[first] + known[second] + known[third] - 6)
			amatr[first][second] = 0
			amatr[second][first] = 0
print(ans if ans < 10 ** 10 else -1)


def bear_three(graph):
	sum_rec = 4000
	for m1 in graph:
		for m2 in graph[m1]:
			for m3 in graph[m2]:
				if m3 in graph[m1]:
					sum_rec = min(sum_rec, len(graph[m1]) + len(graph[m2]) + len(graph[m3]) - 6)
	return sum_rec if sum_rec != 4000 else -1
(n, m) = map(int, input().split())
graph = {}
for i in range(1, n + 1):
	graph[i] = []
for _ in range(m):
	(musk1, musk2) = map(int, input().split())
	graph[musk1].append(musk2)
	graph[musk2].append(musk1)
print(bear_three(graph))


f = lambda : map(int, input().split())
(n, m) = f()
(p, s) = ([], [set() for i in range(n + 1)])
for j in range(m):
	(a, b) = f()
	p += [(a, b, c) for c in s[a].intersection(s[b])]
	s[a].add(b)
	s[b].add(a)
k = [len(s[i]) for i in range(n + 1)]
print(min((k[a] + k[b] + k[c] for (a, b, c) in p)) - 6 if p else -1)


class CF574B:
	M = int(1000000000000.0)

	def __init__(self):
		(n, m) = list(map(int, input().split()))
		self.graph = [set() for _ in range(n + 1)]
		self.edges = []
		for _ in range(m):
			(a, b) = list(map(int, input().split()))
			self.edges += [(a, b)]
			self.graph[a] |= {b}
			self.graph[b] |= {a}

	def solve(self):
		res = self.M
		for (a, b) in self.edges:
			for common in self.graph[a] & self.graph[b]:
				res = min(res, len(self.graph[a]) + len(self.graph[b]) + len(self.graph[common]) - 6)
		print(res if res < self.M else -1)

def main():
	CF574B().solve()

def __starting_point():
	main()
__starting_point()


import math
(n, m) = map(int, input().split())
rede = [[] for _ in range(n)]
somas = [0] * n
vis = [False] * n
ans = math.inf
for __ in range(m):
	(a, b) = map(int, input().split())
	rede[a - 1].append(b - 1)
	rede[b - 1].append(a - 1)
	somas[a - 1] += 1
	somas[b - 1] += 1
for i in range(n):
	vis[i] = True
	for vizinho1 in rede[i]:
		if not vis[vizinho1]:
			for vizinho2 in rede[vizinho1]:
				if vizinho2 != i and i in rede[vizinho2]:
					if ans > somas[i] + somas[vizinho1] + somas[vizinho2]:
						ans = somas[i] + somas[vizinho1] + somas[vizinho2]
						pass
						break
if ans < math.inf:
	print(ans - 6)
else:
	print(-1)


def main():
	mode = 'filee'
	if mode == 'file':
		f = open('test.txt', 'r')
	get = lambda : [int(x) for x in (f.readline() if mode == 'file' else input()).split()]
	[n, m] = get()
	mus = {}
	for z in range(n):
		mus[z + 1] = []
	for z in range(m):
		[x, y] = get()
		mus[x].append(y)
		mus[y].append(x)
	removed = set()
	for i in range(n):
		if len(mus[i + 1]) == 0:
			mus.pop(i + 1)
			continue
		if len(mus[i + 1]) == 1:
			removed.add(i + 1)
	minn = 4500
	found = False
	for i in mus:
		to_check = list(set(mus[i]) - removed)
		for j in range(len(to_check[:-1])):
			if mus[i][j] in removed:
				continue
			for k in range(j + 1, len(to_check)):
				if to_check[j] in mus[to_check[k]]:
					minn = min(minn, len(mus[i]) + len(mus[to_check[j]]) + len(mus[to_check[k]]) - 6)
					found = True
	print(minn if found else '-1')
	if mode == 'file':
		f.close()
main()


(n, m) = map(int, input().split())
t = m
graph = [[] for _ in range(n + 1)]
while t > 0:
	(ai, bi) = map(int, input().split())
	graph[ai].append(bi)
	graph[bi].append(ai)
	t -= 1
min_rec = n * 3
for i in range(1, n - 1):
	if len(graph[i]) < 2:
		continue
	else:
		for j in graph[i]:
			if len(graph[j]) < 2:
				continue
			else:
				for k in graph[j]:
					if k in graph[i]:
						temp = len(graph[i]) + len(graph[j]) + len(graph[k]) - 6
						if temp < min_rec:
							min_rec = temp
if min_rec < n * 3:
	print(min_rec)
else:
	print(-1)


(n, m) = list(map(int, input().split()))
e = [set() for i in range(n + 1)]
E = []
for i in range(m):
	(a, b) = list(map(int, input().split()))
	E.append((a, b))
	e[a] |= {b}
	e[b] |= {a}
l = [0] * (n + 1)
for i in range(n + 1):
	l[i] = len(e[i])
lmin = 12000
for (a, b) in E:
	t = e[a] & e[b]
	for x in t:
		if a in e[x] and b in e[x]:
			w = l[a] + l[b] + l[x] - 6
			if lmin > w:
				lmin = w
print(-1 if lmin == 12000 else lmin)


from collections import defaultdict as dd
INF = int(10000000.0)
MAX_N = 4001
graph_adj = [[0] * MAX_N for _ in range(MAX_N)]
degree = [0] * MAX_N
(nodes, edges) = map(int, input().split())
for edge in range(edges):
	(a, b) = map(int, input().split())
	graph_adj[a][b] = 1
	graph_adj[b][a] = 1
	degree[a] += 1
	degree[b] += 1
output = INF
for i in range(nodes + 1):
	for j in range(i + 1, nodes + 1):
		if graph_adj[i][j]:
			for k in range(j + 1, nodes + 1):
				if graph_adj[i][k] and graph_adj[j][k]:
					output = min(output, degree[i] + degree[j] + degree[k])
if output == INF:
	print('-1')
else:
	print(f'{output - 6}')


def dfs(no_at, pai, princ, i):
	if i == 3:
		if princ in adj[no_at]:
			x = len(adj[princ]) - 2
			y = len(adj[pai]) - 2
			z = len(adj[no_at]) - 2
			s = x + y + z
			global menor
			if menor > s:
				menor = s
		return
	for child in adj[no_at]:
		if child == pai:
			continue
		if len(adj[child]) < 2:
			continue
		dfs(child, no_at, princ, i + 1)
(m, n) = map(int, input().split())
adj = [set() for i in range(m + 1)]
for i in range(n):
	(a, b) = map(int, input().split())
	adj[a].add(b)
	adj[b].add(a)
menor = float('inf')
for i in range(1, m + 1):
	if len(adj[i]) >= 2:
		dfs(i, i, i, 1)
print(-1) if menor == float('inf') else print(menor)


(n, m) = list(map(int, input().split()))
adj = {}

def minSum(adj):
	sum = 4001
	for i in adj:
		for j in adj[i]:
			for k in adj[j]:
				if k in adj[i]:
					sum = min(len(adj[i]) + len(adj[j]) + len(adj[k]), sum)
	return sum
for i in range(m):
	(x, y) = list(map(int, input().split()))
	if x in adj:
		adj[x].append(y)
	else:
		adj[x] = [y]
	if y in adj:
		adj[y].append(x)
	else:
		adj[y] = [x]
res = minSum(adj)
if res == 4001:
	print('-1')
else:
	print(res - 6)


from sys import stdin
(n, m) = map(int, stdin.readline().split())
g = [set() for i in range(n)]
for _ in range(m):
	(i, j) = map(int, stdin.readline().split())
	g[i - 1].add(j - 1)
	g[j - 1].add(i - 1)
m = float('inf')
for i in range(len(g) - 1):
	wi = len(g[i])
	for j in range(1, len(g)):
		wj = len(g[j])
		if i in g[j] and j in g[i]:
			rs = list(map(lambda x: len(g[x]), g[i].intersection(g[j])))
			if len(rs) > 0:
				m = min(m, min(rs) + wi + wj)
print(m - 6 if m != float('inf') else -1)


def Solve(graph):
	cycles = []
	for vertex in graph:
		cycle = [vertex]
		for kid1 in graph[vertex]:
			cycle = [vertex, kid1]
			for kid2 in graph[vertex]:
				if kid2 in graph[kid1]:
					cycle.append(kid2)
					cycles.append(cycle)
					cycle = [vertex, kid1]
	min_degree = float('inf')
	for cycle in cycles:
		total = 0
		for i in cycle:
			total += len(graph[i])
		if total < min_degree:
			min_degree = total
	if min_degree == float('inf'):
		print(-1)
		return
	print(min_degree - 6)

def main():
	(n, m) = map(int, input().split())
	graph = {}
	for i in range(1, n + 1):
		graph[i] = []
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	Solve(graph)
main()


(n, m) = map(int, input().split())
solutions = []
recognitions = []
knowledges = []
for i in range(n + 1):
	knowledges.append(set())
	recognitions.append(0)
for i in range(m):
	(x, y) = map(int, input().split())
	for j in knowledges[x].intersection(knowledges[y]):
		solutions.append((x, y, j))
	knowledges[x].add(y)
	knowledges[y].add(x)
	recognitions[x] += 1
	recognitions[y] += 1
result = -1
for i in solutions:
	sum = recognitions[i[0]] + recognitions[i[1]] + recognitions[i[2]] - 6
	if result > 0:
		result = min(result, sum)
	else:
		result = sum
print(result)


I = lambda : map(int, input().split())
(n, m) = I()
g = [set() for _ in range(n)]
for _ in range(m):
	(a, b) = I()
	g[a - 1].add(b - 1)
	g[b - 1].add(a - 1)
result = 99999
for i in range(n):
	for j in g[i]:
		for k in g[j]:
			if k in g[i]:
				result = min(result, len(g[i]) + len(g[j]) + len(g[k]) - 6)
if result == 99999:
	print(-1)
else:
	print(result)


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
from math import inf

def solve(a, b, c, d):
	if b in d[c]:
		return len(d[a]) + len(d[b]) + len(d[c]) - 6
	else:
		return inf

def main():
	(n, m) = map(int, input().split())
	d = dict()
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a not in d:
			d[a] = []
		if b not in d:
			d[b] = []
		d[a].append(b)
		d[b].append(a)
	ans = inf
	for item in d.keys():
		l = d[item]
		z = len(l)
		if z >= 2:
			for i in range(len(l)):
				for j in range(i + 1, len(l)):
					ans = min(ans, solve(item, l[i], l[j], d))
	if ans == inf:
		print(-1)
	else:
		print(ans)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
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')

def nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
G = [[0] * n for _ in range(n)]
deg = [0] * n
edges = []
for _ in range(m):
	(a, b) = map(int, input().split())
	G[a - 1][b - 1] = 1
	G[b - 1][a - 1] = 1
	deg[a - 1] += 1
	deg[b - 1] += 1
	edges.append((a - 1, b - 1))
ans = 10 ** 18
for (a, b) in edges:
	for c in range(n):
		if c != a and c != b and (G[a][c] == 1) and (G[b][c] == 1):
			ans = min(ans, deg[a] + deg[b] + deg[c] - 6)
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


(n, m) = map(int, input().split())
e = [set() for i in range(n + 1)]
E = []
mi = 1000000000000
for i in range(m):
	(a, b) = map(int, input().split())
	E += [(a, b)]
	e[a] |= {b}
	e[b] |= {a}
l = [len(e[i]) for i in range(n + 1)]
for (a, b) in E:
	t = e[a] & e[b]
	for x in t:
		if a in e[x] and b in e[x]:
			k = l[a] + l[b] + l[x] - 6
			if k < mi:
				mi = k
print(-1 if mi == 1000000000000 else mi)


(n, m) = map(int, input('').split())
edge_list = {i: [] for i in range(1, n + 1)}
for i in range(m):
	(start, end) = map(int, input('').split())
	edge_list[start].append(end)
	edge_list[end].append(start)

def ex(vertice, start, depth, visited, min_recog, backtrack):
	if depth == 2:
		if start in edge_list[vertice]:
			curr_recog = len(edge_list[backtrack[0]]) + len(edge_list[backtrack[1]]) + len(edge_list[backtrack[2]])
			if curr_recog < min_recog:
				min_recog = curr_recog
		backtrack.pop()
		visited.pop()
		depth -= 1
		return (depth, min_recog)
	else:
		for child in edge_list[vertice]:
			if child not in visited:
				depth += 1
				backtrack.append(child)
				visited.append(child)
				(depth, min_recog) = ex(child, start, depth, visited, min_recog, backtrack)
	depth -= 1
	backtrack.pop()
	visited.pop()
	return (depth, min_recog)
triangles = []

def search():
	min_recog = float('inf')
	explored = set()
	for vertice in edge_list:
		if not set(edge_list[vertice]).issubset(explored):
			visited = []
			back_track = []
			back_track.append(vertice)
			visited.append(vertice)
			explored.add(vertice)
			(depth, min_recog) = ex(vertice, vertice, 0, visited, min_recog, back_track)
	return min_recog
min_recog = search()
if min_recog == float('inf'):
	print('-1')
else:
	print(min_recog - 6)


input_values = input().split()
n = int(input_values[0])
m = int(input_values[1])
number_of_pairs = m
values = []
for i in range(n + 1):
	values.append([])
while number_of_pairs > 0:
	input_values = input().split()
	ai = int(input_values[0])
	bi = int(input_values[1])
	values[ai].append(bi)
	values[bi].append(ai)
	number_of_pairs -= 1
min_sum = n * 3
for i in range(1, n - 1):
	if len(values[i]) >= 2:
		for j in values[i]:
			if len(values[j]) >= 2:
				for k in values[j]:
					if k in values[i]:
						aux = len(values[i]) + len(values[j]) + len(values[k]) - 6
						if aux < min_sum:
							min_sum = aux
if min_sum < n * 3:
	print(min_sum)
else:
	print(-1)