CF542E.Playing on Graph

Vova and Marina love offering puzzles to each other. Today Marina offered Vova to cope with the following task.

Vova has a non-directed graph consisting of n vertices and m edges without loops and multiple edges. Let's define the operation of contraction two vertices a and b that are not connected by an edge. As a result of this operation vertices a and b are deleted and instead of them a new vertex x is added into the graph, and also edges are drawn from it to all vertices that were connected with a or with b (specifically, if the vertex was connected with both a and b, then also exactly one edge is added from x to it). Thus, as a result of contraction again a non-directed graph is formed, it contains no loops nor multiple edges, and it contains (n - 1) vertices.

Vova must perform the contraction an arbitrary number of times to transform the given graph into a chain of the maximum length. A chain of length k (k ≥ 0) is a connected graph whose vertices can be numbered with integers from 1 to k + 1 so that the edges of the graph connect all pairs of vertices (i, i + 1) (1 ≤ i ≤ k) and only them. Specifically, the graph that consists of one vertex is a chain of length 0. The vertices that are formed as a result of the contraction are allowed to be used in the following operations of contraction.

The picture illustrates the contraction of two vertices marked by red.

Help Vova cope with his girlfriend's task. Find the maximum length of the chain that can be obtained from the resulting graph or else determine that it is impossible to obtain the chain.

沃娃和玛丽娜喜欢互相出谜题。今天，玛丽娜给沃娃出了如下一道题。

沃娃有一个包含 $n$ 个顶点和 $m$ 条边的无向图，图中不含自环与重边。我们定义一种“收缩”操作：对两个不相邻的顶点 $a$ 和 $b$ 进行收缩。该操作的结果是：删除顶点 $a$ 和 $b$，并在图中新增一个顶点 $x$；同时，从 $x$ 向所有原先与 $a$ 或 $b$ 相邻的顶点连边（特别地，若某顶点原先同时与 $a$ 和 $b$ 相邻，则仅向其连一条边）。因此，收缩后得到的仍是一个无向图，不含自环与重边，且顶点数为 $n-1$。

沃娃需执行任意次数的收缩操作，将给定图变换为一条尽可能长的链。长度为 $k$（$k \geq 0$）的链是指一个连通图，其顶点可被编号为 $1$ 到 $k+1$ 的整数，使得图中的边恰好连接所有形如 $(i,\, i+1)$ 的顶点对（其中 $1 \leq i \leq k$），且仅连接这些顶点对。特别地，仅含一个顶点的图是一条长度为 $0$ 的链。由收缩操作产生的新顶点允许在后续收缩操作中继续使用。

图中展示了两个标为红色的顶点的收缩过程。

请帮助沃娃完成他女友布置的任务：求出能从原图通过收缩操作得到的链的最大可能长度；若无法得到链，则判定其不可能。

The first line contains two integers n, m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the original graph.

Next m lines contain the descriptions of edges in the format a__i, b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i), which means that there is an edge between vertices a__i and b__i. It is guaranteed that there is at most one edge between each pair of vertexes.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 1000$，$0 \leq m \leq 100\,000$）—— 分别表示原图的顶点数和边数。

接下来 $m$ 行，每行描述一条边，格式为 $a_i,\,b_i$（$1 \leq a_i,\,b_i \leq n$，$a_i \neq b_i$），表示顶点 $a_i$ 与 $b_i$ 之间存在一条边。保证任意一对顶点之间至多只有一条边。

If it is impossible to obtain a chain from the given graph, print  - 1. Otherwise, print the maximum possible number of edges in the resulting chain.

如果无法从给定图中得到一条链，则输出 $-1$。否则，输出所得链中可能的最大边数。

In the first sample test you can contract vertices 4 and 5 and obtain a chain of length 3.

In the second sample test it is initially impossible to contract any pair of vertexes, so it is impossible to achieve the desired result.

In the third sample test you can contract vertices 1 and 2 and obtain a chain of length 2.

在第一个样例测试中，你可以收缩顶点 4 和 5，从而得到一条长度为 3 的链。

在第二个样例测试中，初始状态下无法收缩任意一对顶点，因此不可能达到目标结果。

在第三个样例测试中，你可以收缩顶点 1 和 2，从而得到一条长度为 2 的链。