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 的链。