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