Small Cycles

After reviewing the proposed competition problems, the zebra Hippo noticed that the maximum test for one of the problems features a graph with too few edges. This test involves an undirected graph (G) with the following characteristics:

• (G) is a simple graph, meaning it has no loops or multiple edges.

• (G) is connected.

• (G) contains no simple cycles of length 4 or more. A sequence of (k) distinct vertices (v_1, ..., v_k) forms a simple cycle of length (k) if each vertex (v_i) is connected to (v_i+1) by an edge, and (v_1) is also connected to (v_k) by an edge.

The zebra Hippo wants to add more edges to this graph while ensuring these properties remain intact. How many additional edges can be added?

Input

The first line of the input contains two integers (V) ((1 $\le$ V $\le$ 10^5)) and (E) ((0 $\le$ E $\le$ 10^5)), separated by a space. Here, (V) is the number of vertices in graph (G), and (E) is the number of edges in graph (G).

The next (E) lines describe the edges of the graph. The (i)-th line contains two integers (a_i) and (b_i) ((1 $\le$ a_i < b_i $\le$ V)), separated by a space, indicating that vertices (a_i) and (b_i) are connected by the (i)-th edge. The vertices are numbered from 1 to (V). It is guaranteed that (G) meets the properties outlined in the problem statement.

Output

Output the maximum number of edges that the zebra Hippo can add to graph (G) while maintaining the specified properties.

Examples