Problem Statement

Rng has a connected undirected graph with $N$ vertices. Currently, there are $M$ edges in the graph, and the $i$-th edge connects Vertices $A_i$ and $B_i$.

Rng will add new edges to the graph by repeating the following operation:

• Operation: Choose $u$ and $v$ $(u \\neq v)$ such that Vertex $v$ can be reached by traversing exactly three edges from Vertex $u$, and add an edge connecting Vertices $u$ and $v$. It is not allowed to add an edge if there is already an edge connecting Vertices $u$ and $v$.

Find the maximum possible number of edges that can be added.

Constraints

• $2 \\leq N \\leq 10^5$
• $1 \\leq M \\leq 10^5$
• $1 \\leq A_i,B_i \\leq N$
• The graph has no self-loops or multiple edges.
• The graph is connected.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_M$ $B_M$

Output

Find the maximum possible number of edges that can be added.

Sample Input 1

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

Sample Output 1

4

If we add edges as shown below, four edges can be added, and no more.

Sample Input 2

5 5
1 2
2 3
3 1
5 4
5 1

Sample Output 2

5

Five edges can be added, for example, as follows:

• Add an edge connecting Vertex $5$ and Vertex $3$.
• Add an edge connecting Vertex $5$ and Vertex $2$.
• Add an edge connecting Vertex $4$ and Vertex $1$.
• Add an edge connecting Vertex $4$ and Vertex $2$.
• Add an edge connecting Vertex $4$ and Vertex $3$.