An undirected graph is called a *dumbbell* if its vertices can be
partitioned into ~2~ parts, such that:

Each pair of vertices in the same part are connected by an edge.

There exists exactly one edge that connects two vertices in different parts.

The following graphs are *dumbbells*:

The following graphs are **not** *dumbbells*:

The leftmost graph cannot be partitioned into two parts connected by an edge. In the middle graph, there is one part in which not all pairs of vertices are connected by an edge. The rightmost graph is not connected.

You are given an undirected graph with ~N~ vertices and ~M~ edges. The
graph is simple: There is no self-loops, and there is no more than one
edge between any pair of vertices. Calculate the least number of edges
needed to add into the graph so that it becomes a *dumbbell*.

#### Input

The first line contains two integers ~n~ and ~m~ (~2 \le n \le 10^5~, ~0 \le m \le 10^5~), the number of vertices and edges of the given graph, respectively.

Each of the following ~m~ lines contain two integers ~u~ and ~v~ (~1 \le u, v \le n~, ~u \ne v~), denoting an edge between ~u~ and ~v~.

It is guaranteed that no two edges connect the same pair of vertices.

#### Output

Output a single integer, the least number of edges needed to add into
the graph so that it becomes a *dumbbell*.

If there is no way to add edges to make the graph a *dumbbell*, output
~-1~.

#### Scoring

Subtask 1 (~125~ points): ~n \le 500~

Subtask 2 (~285~ points): No additional constraints

The total score for this problem is ~410~.

#### Sample Input 1

```
5 7
2 3
5 3
2 5
2 1
1 5
3 1
5 4
```

#### Sample Output 1

```
0
```

#### Sample Input 2

```
7 5
5 7
2 4
1 3
5 1
5 6
```

#### Sample Output 2

```
5
```

#### Sample Input 3

```
3 3
1 2
2 3
3 1
```

#### Sample Output 3

```
-1
```

## Comments