You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Three-on-three basketball originated from street games among African American children in the United States. Currently, there are $n$ players, and $m$ pairs of players know each other. The popularity of a player is defined as the number of people who know him.
The coach needs to select three players from these $n$ players to form a "dark horse" team for the competition. The three players must all know each other, but the coach wants the sum of their popularity to be as low as possible, hoping for a "stunning" performance.

Input Format

The first line contains two integers $n$ and $m$, both not greater than $4000$.
The next $m$ lines each contain two integers $x$ and $y$ ($x < y$), indicating that player $x$ and player $y$ know each other (there may be duplicate relationships in the data).
For $50\%$ of the data, $n, m \leq 200$.
For $100\%$ of the data, $n, m \leq 40000$.

Output Format

If you can find three players who all know each other, output the minimum possible sum of their popularity among all such choices; otherwise, output $-1$.

Sample

5 6
1 2
1 3
2 3
2 4
3 4
4 5

8