The Road System of Uzlandia#7242
Uzlandia is a magnificent country with cities, numbered from to , connected by roads. Each road links two distinct cities and allows travel in both directions. There is at most one road between any pair of cities.
Since ancient times, Uzlandia's road system has adhered to a unique property known as oddness. Originally maintained for religious reasons, this tradition continues today, much like the custom of presenting an odd number of flowers in a bouquet.
Let us define the property of oddness:
A sequence of city numbers C_1, \ldots, C_K (K \geq 2) is called a path if for every adjacent pair C_i, C_{i+1} (C_i \neq C_{i+1}, 1 \leq i < K), there is a road connecting city C_i and city C_{i+1}. If C_1 = C_K, the path is called closed. The length of a path C_1, \ldots, C_K is .
The rule of oddness states that in Uzlandia, all closed paths must have an odd length. That is, there is no closed path of even length.
The road network in Figure satisfies the property of oddness. The system in Figure does not satisfy this property, as there exists a closed path of even length : 1 \to 2 \to 4 \to 1.
Recently, the Minister of Transport of Uzlandia decided to enhance the road network's efficiency by constructing additional roads. However, the new network must still adhere to the property of oddness. All new roads must connect different cities, and there must be no more than one road between any pair of cities in the new network.
A substantial budget has been allocated for this project, so the Minister wants to add as many new roads as possible while maintaining the oddness property. However, this task is challenging, so the Ministry of Transport seeks your expertise.
You are given a description of the current road network. Your task is to determine the maximum number of roads that can be added without violating the property of oddness.
The first line contains the integers (1 \leq N \leq 10\ 000) and (0 \leq M \leq 100\ 000).
The following lines each describe a road in Uzlandia. Each line contains two integers and (1 \leq X, Y \leq N,\ X \neq Y), denoting that there is a road between city and city .
It is guaranteed that the existing road system satisfies the property of oddness, and there is at most one road between any two cities.
Output a single integer — the maximum number of roads that can be added to the existing road network.
Example 1
The road network from the first example is shown in Figure . The road network from the second example is shown in Figure , and its state after adding new roads is shown in Figure .
In the second example, new roads can be added: -, -, -, -, -.