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: interview

Starter code:

Solutions:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# AUTHOR: haya14busa
import sys
import io

from collections import defaultdict
from itertools import combinations


def solve(n, m, pairs):
    # return: minimum possible sum of their recognitions
    assert 3 <= n <= 4000  # number of warioor
    assert 0 <= m <= 4000  # number of pairs of warriors knowing each other
    # for (a, b) in pairs:
    #     assert 1 <= a < b <= n 

    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()))
    # return 'YES' if solve(*getinput()) else 'NO' # for boolean output
    # return '\n'.join(map(str, solve(*getinput()))) # for multiple line output


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 = [

        (
            # INPUT
            '''\
5 6
1 2
1 3
2 3
2 4
3 4
4 5
            ''',
            # EXPECT
            '''\
2
            '''
        ),

        (
            # INPUT
            '''\
7 4
2 1
3 6
5 1
1 7
            ''',
            # EXPECT
            '''\
-1
            '''
        ),


    ]

    # List[(List[arg for solve()], expect)]
    TEST_CASES = [
        # ([], None),
    ]

    # You do need to see below
    import unittest  # to save memory, import only if test required
    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())
        # art.float_equal(float(iosolve()), float(expect.strip()), 10 ** -6)


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

def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python
# 574B_musk.py - Codeforces.com 574B Musk program by Sergey 2015

import unittest
import sys

###############################################################################
# Musk Class
###############################################################################


class Musk:
    """ Musk representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        self.n, self.m = list(map(int, uinput().split()))

        # Reading multiple lines of pairs
        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)]

        # Array of sets
        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):
        """ Main calcualtion function of the class """

        result = self.min_rank

        return str(result)

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Musk class testing """

        # Constructor test
        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})

        # Sample test
        self.assertEqual(Musk(test).calculate(), "2")

        # Sample test
        test = "7 4\n2 1\n3 6\n5 1\n1 7"
        self.assertEqual(Musk(test).calculate(), "-1")

        # Sample test
        test = "1\n1 2\n1"
        # self.assertEqual(Musk(test).calculate(), "0")

        # My tests
        test = "1\n1 2\n1"
        # self.assertEqual(Musk(test).calculate(), "0")

        # Time limit test
        # self.time_limit_test(5000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        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"

        # Run the test
        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():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Musk().calculate())

__starting_point()

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

import sys

lines = sys.stdin.read().split("\n")
# n, k = map(int, lines[0].split(" "))
# n = int(lines[0])
# nums = list(map(int, lines[1].split(" ")))


n, m = list(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 = list(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=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())
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)

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)

# print(adj)

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)


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)

n, m = list(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 = list(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)


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)

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


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 = 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 = list(map(int,input().split()))
e = [set() for i in range(n+1)] #khoi tao mang e chua cac tap hop chua dinh ke
                                # index tu 1 den n tuong ung voi cac dinh
E=[]                            # khoi tao mang E chua 2 dinh co quan he
for i in range(m):
    a,b = list(map(int, input().split()))
    E.append((a,b))             # dua (a,b) vao mang chua 2 dinh co qan he
    e[a]|={b}                   # dua b vao tap hop dinh ke dinh a
    e[b]|={a}                   # dua a vao tap dinh ke dinh b
                                # |= la phep hop tap hop

l = [0]*(n+1)
for i in range(n+1):
    l[i] = len(e[i])            #l[i] so dinh ke voi dinh i

lmin = 12000
    
#xu li
# xet tung cap dinh co quan he (a,b). lay giao cua 2 tap hop e[a],e[b]
# xet tung phan tu x trong tap hop giao xem e[x] co chua a,b hay ko?

for a,b in E:
    t = e[a]&e[b]               # & phep giao tap hop
    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)


class CF574B:
    M = int(1e12)   # $$ +\infty $$

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

def main():
    M = int(1e12)  # $$ +\infty $$

    n, m = list(map(int, input().split()))
    graph = [set() for _ in range(n + 1)]
    edges = []
    for _ in range(m):
        a, b = list(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)


def __starting_point():
    main()

__starting_point()

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)



import itertools

n,m = list(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)


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)

# print(adj)

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





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


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)


#!/usr/bin/env python3
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] # smallest degree
    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))



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
  # puts "visited: #{u} #{adju}"
  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:
        # print(u, v, p, graph.adj(u), graph.adj(v), graph.adj(p), rps[u], rps[v], rps[p])
        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 = list(map(int, input().split()))
Es = [set() for i in range(n)]
edges = set()
for i in range(m):
    a, b = list(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)