Three Friends

Interview

Time limit2sMemory limit512 MB

Summary

Given a sparse undirected graph, find three mutually adjacent vertices minimizing the sum of their degrees excluding the other two chosen vertices.

Level: Medium4 of 10
Topics: Graph, Brute force, Array, Implementation
Solved: No attempts yet

Problem

There are N people, and we want to choose three of them, A, B, and C. All three must be friends with one another.

There can be very many ways to choose the three people. We want the value A's friend count + B's friend count + C's friend count to be as small as possible. When computing the sum of friend counts, the three people are excluded. That is, when counting A's friends, B and C are excluded; when counting B's friends, A and C are excluded; when counting C's friends, A and B are excluded.

Input

The first line gives the number of people N (3 ≤ N ≤ 4,000) and the number of friendships M (0 ≤ M ≤ 4,000). The next M lines each give two integers A and B describing a friendship. A friendship means A and B, and B and A, are friends.

People are numbered from 1 to N. The same friendship is never given more than once.

Output

On the first line, print the minimum value of A's friend count + B's friend count + C's friend count. If no three people can be chosen under the conditions of the problem, print -1.

Examples2

Example 1
Input
```
5 6
1 2
1 3
2 3
2 4
3 4
4 5
```
Expected output
```
2
```
Example 2
Input
```
7 4
2 1
3 6
5 1
1 7
```
Expected output
```
-1
```