AT_arc099_c.[ARC099E] Independence

在 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$

请输出答案。

限制条件

• $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 翻译