Problem Description

Ringo has a connected undirected graph with \( N \) vertices. The graph already has \( M \) edges, where the \( i \)-th edge connects vertex \( A_i \) and vertex \( B_i \).

Ringo wants to add more edges by performing the following operation:

• Operation: Take vertices \( u \) and \( v \) (\( u \neq v \)) such that vertex \( v \) can be reached from vertex \( u \) by exactly 3 edges. Add an edge between vertex \( u \) and vertex \( v \), provided that there is no edge between vertex \( u \) and vertex \( v \) already.

Determine the maximum number of edges Ringo can add.

Input Format

The input is given from the standard input in the following format:

\( N \) \( M \) \( A_1 \) \( B_1 \) \( A_2 \) \( B_2 \) \( : \) \( A_M \) \( B_M \)

Output Format

Output the maximum number of edges that can be added.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

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

Sample Output #2

5

Notes/Hints

Constraints

• \( 2 \leq N \leq 10^5 \)
• \( 1 \leq M \leq 10^5 \)
• \( 1 \leq A_i, B_i \leq N \)
• There are no multiple edges or self-loops.
• The given graph is connected.

Sample Explanation 1

By adding edges as shown in the figure below, it is possible to add 4 edges, and no more edges can be added. 

Sample Explanation 2

For example, by adding edges in the following order, it is possible to add 5 edges:
- Add an edge between vertex \( 5 \) and vertex \( 3 \).
- Add an edge between vertex \( 5 \) and vertex \( 2 \).
- Add an edge between vertex \( 4 \) and vertex \( 1 \).
- Add an edge between vertex \( 4 \) and vertex \( 2 \).
- Add an edge between vertex \( 4 \) and vertex \( 3 \).

见题面 Input 部分

见题面 Output 部分