问题描述

在 AtCoderian 联邦的 Takahashi 省份中，有 $N$ 个城市，编号为$1, 2, ..., N$。有 $M$ 条双向道路连接了这些城市。第 $i$ 条道路连接了城市 $A_i$ 和城市 $B_i$。每条道路连接两个不同的城市。此外，对于任意两个城市，至多只有一条直接连接它们的道路。

有一天，决定将 Takahashi 省份分成两个省份：Taka 和 Hashi。分割后，Takahashi 中的每个城市都属于 Taka 或 Hashi 中的一种。所有城市都属于 Taka 或者所有城市都属于 Hashi 都是可以接受的。满足以下条件：

• 同一个省份（Taka 或 Hashi）中的任意两个城市之间都由一条道路直接连接。

找出端点城市属于同一个省份的道路的最小数量。如果不能将城市划分为 Taka 和 Hashi，使得条件成立，则打印 -1。

约束条件

• $2 \leq N \leq 700$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i \leq N$
• $1 \leq B_i \leq N$
• $A_i \neq B_i$
• 如果 $i \neq j$，至少满足以下之一：$A_i \neq A_j$ 和 $B_i \neq B_j$。
• 如果 $i \neq j$，至少满足以下之一：$A_i \neq B_j$ 和 $B_i \neq A_j$。

输入

输入格式如下，从标准输入读取：

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_M$ $B_M$

输出

输出答案。

示例输入 1

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

示例输出 1

4

例如，如果城市 $1, 2$ 属于 Taka，城市 $3, 4, 5$ 属于 Hashi，则条件得到满足。在这种情况下，端点城市属于同一个省份的道路数量为 $4$。

示例输入 2

5 1
1 2

示例输出 2

-1

在这个示例中，无论城市属于哪个省份，都无法满足条件。

示例输入 3

4 3
1 2
1 3
2 3

示例输出 3

3

示例输入 4

10 39
7 2
7 1
5 6
5 8
9 10
2 8
8 7
3 10
10 1
8 10
2 3
7 4
3 9
4 10
3 4
6 1
6 7
9 5
9 7
6 9
9 4
4 6
7 5
8 3
2 5
9 2
10 7
8 6
8 9
7 3
5 3
4 5
6 3
2 10
5 10
4 2
6 2
8 4
10 6

示例输出 4

21