题目描述

在 AtCoder 联邦的高桥州，有 $N$ 个城市。城市编号为 $1, 2, \ldots, N$。这些城市之间通过 $M$ 条双向道路相连。第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$。每条道路都连接两个不同的城市，并且任意两座城市之间至多只有一条直接相连的道路。

某时，高桥州将被分为两个州：高州和桥州。分离后，每个城市将属于高州或桥州中的一个。允许所有城市都属于同一个州。

现在希望满足以下条件：

• 在高州和桥州中，任意两个属于同一州的城市之间都直接有道路相连。

请你求出，在满足上述条件的分配方案中，使得两端城市属于同一州的道路数量的最小值。如果无法满足条件，则输出 $-1$。

输入格式

输入通过标准输入给出，格式如下：

$N\ M$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_M\ B_M$

输出格式

请输出答案。

样例 1

输入

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

输出

4

样例 2

输入

5 1
1 2

输出

-1

样例 3

输入

4 3
1 2
1 3
2 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

输出

21

说明/提示

限制条件

• $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$ 成立

样例解释 1

例如，将城市 $1, 2$ 分配给高州，将城市 $3, 4, 5$ 分配给桥州，可以满足条件。此时，两端城市属于同一州的道路数量为 $4$。

样例解释 2

在这个例子中，无论如何分配城市，都无法满足条件。

由 ChatGPT 4.1 翻译