RabbitWalking

Time limit8sMemory limit512 MB

Summary

Given a simple undirected graph, add the maximum number of edges so no closed walk of odd length exists, or print -1 if the graph is already bipartite.

Level: Medium7 of 10
Topics: Graph, Union-find, BFS, Greedy
Solved: No attempts yet

Problem

The city where the rabbit lives has $V$ intersections and $E$ roads. The intersections are numbered starting from 1. The $i$ -th road connects intersection $a_i$ and intersection $b_i$ in both directions.

The rabbit likes walking and odd numbers. The rabbit wants to take a walk along a route that starts at some intersection, follows an odd number of roads, and returns to the starting vertex.

The cat, who is the mayor of this city, wants to add many roads connecting distinct pairs of intersections to make travel within the city more efficient. For any pair of intersections, at most one road can be built. The cat is also mischievous, so the cat wants the city to contain no route that follows an odd number of roads and returns to the starting vertex.

Find the maximum number of roads that can be added. If the rabbit's requirement is already satisfied from the start, output -1.

Input

The input is given in the following format:

$V$ $E$

$a_1$ $b_1$

...

$a_E$ $b_E$

Output

Print one integer on a single line: the maximum number of roads that can be added. If the rabbit's requirement is already satisfied from the start, print -1.

Constraints

$V$ is between 1 and 100,000, inclusive.
$E$ is between 0 and 100,000, inclusive.
$a_i$ and $b_i$ are distinct.
No two roads connect the same pair of intersections.

Examples2

Example 1
Input
```
8 5
1 2
6 5
6 4
1 3
4 7
```
Expected output
```
11
```
Example 2
Input
```
5 8
2 1
2 4
1 3
5 4
4 1
2 3
3 5
2 5
```
Expected output
```
-1
```