← 返回题目列表

AtCoder · arc099_c

E. 独立

中文机器翻译题面 查看原题

分数: 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