Score : $500$ points

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.

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

4

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

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

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$.