← 返回题目列表

Codeforces · 542/E

E. 在图表上播放

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

Vova 和 Marina 喜欢互相提供拼图。今天,Marina 向 Vova 提出了以下任务。

Vova 有一个由 n 个顶点和 m 个边组成的无向图,没有循环和多条边。我们来定义收缩两个没有边连接的顶点a和b的操作。此操作的结果是,顶点 a 和 b 被删除,取而代之的是,新的顶点 x 被添加到图中,并且从该顶点向与 a 或 b 连接的所有顶点绘制边(具体来说,如果该顶点与 a 和 b 都连接,则也从 x 向其添加恰好一条边)。因此,由于再次收缩,形成了一个无向图,它不包含环,也不包含多条边,并且包含 (n - 1) 个顶点。

Vova 必须执行任意次数的收缩,才能将给定的图转换为最大长度的链。长度为 k (k ≥ 0) 的链是一个连通图,其顶点可以用从 1 到 k + 1 的整数进行编号,以便图的边连接所有顶点对 (i, i + 1) (1 ≤ i ≤ k) 并且仅连接它们。具体来说,由一个顶点组成的图是一条长度为0的链。由于收缩而形成的顶点允许用于后续的收缩操作。

该图展示了红色标记的两个顶点的收缩。

帮助 Vova 处理女友的任务。从得到的图中求出能得到的链的最大长度,否则判定无法得到该链。

输入

第一行包含两个整数 n, m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 100 000) — 原始图中的顶点数和边数。

接下来的 m 行包含边的描述,格式为 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi),这意味着顶点 ai 和 bi 之间有一条边。保证每对顶点之间至多有一条边。

输出

如果无法从给定图中获得链,则打印 - 1。否则,打印结果链中可能的最大边数。

示例

输入 #1

5 4
1 2
2 3
3 4
3 5

输出 #1

3

输入 #2

4 6
1 2
2 3
1 3
3 4
2 4
1 4

输出 #2

-1

输入 #3

4 2
1 3
2 4

输出 #3

2

注意

在第一个示例测试中,您可以收缩顶点 4 和 5 并获得长度为 3 的链。

在第二个样本测试中,最初不可能收缩任何一对顶点,因此不可能达到预期的结果。

在第三个示例测试中,您可以收缩顶点 1 和 2 并获得长度为 2 的链。