分数: 700 点
问题陈述
在 AtCoderian 联邦的高桥州,有 N 城市,编号 1, 2, ..., N. M 双向道路连接这些城市。 的 i第条路连接城市 A_i 和城市 B_i。 每条道路都连接两个不同的城市。 另外,对于任意两个城市,最多有一条道路 直接 直接地 连接它们。
有一天,决定将高桥州分为高桥州和桥州两个州。 分割后,高桥的各个城市将属于高桥或桥。 可以接受所有城市都属于塔卡,或者所有城市都属于哈市。 这里,应满足以下条件:
- 同一州的任意两个城市塔卡或哈希市均由道路直接连接。
求端点城市属于同一州的最小可能数量的道路。
如果无法将城市划分为 Taka 和 Hashi 从而满足条件,则打印 -1.
约束
- 2 \leq N \leq 700
- 0 \leq M \leq N(N-1)/2
- 1 \leq A_i \leq N
- 1 \leq B_i \leq N
- A_i \neq B_i
- If i \neq j,至少满足以下条件之一: A_i \neq A_j 和 B_i \neq B_j.
- If 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 属于塔卡和城市 3, 4, 5 属于哈市,条件满足。 这里,端点城市属于同一州的道路数量为 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