The Road System of Uzhlândia
Uzlandia is a magnificent country with N cities, numbered from 1 to N, connected by M roads. Each road links two distinct cities and allows travel in both directions. Importantly, 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's define the property of oddness:
A sequence of city numbers C_1,..., C_K (K ≥ 2) is called a path if for every adjacent pair C_i, C_i+1 (C_i ≠ C_i+1, for 1 ≤ i < K), there is a road connecting cities C_i and C_i+1. If C_1 = C_K, the path is termed closed. The length of the path C_1, ..., C_K is defined as K. The rule of oddness dictates that all closed paths in Uzlandia must have an odd length, meaning no closed path can have an even length.
The road network in Figure 1 satisfies the property of oddness, whereas the system in Figure 2 does not, due to the presence of a closed path of even length 4: 1 2 4 1.
Recently, the Minister of Transport of Uzlandia decided to enhance the road system's efficiency by constructing additional roads. However, the new road network must still adhere to the property of oddness. All new roads must connect different cities, and there should be no more than one road between any pair of cities in the new network.
A substantial budget has been allocated for this project, and the Minister aims to add as many new roads as possible while maintaining the specified conditions. However, this task is challenging, prompting the Ministry of Transport to seek your expertise.
You are provided with a description of the current road network. Your task is to determine the maximum number of roads that can be added without violating the oddness property.
Input format: The first line contains the integers N (1 ≤ N ≤ 10,000) and M (0 ≤ M ≤ 100,000). The following M lines describe the roads in Uzlandia. Each line contains two integers X and Y (1 ≤ X, Y ≤ N, X ≠ Y), representing the cities connected by the road. Cities are numbered from 1 to N.
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 format: Output a single integer representing the maximum number of roads that can be added to the existing network.
Explanation of examples:
The road network from the first example is shown in Figure 1. The initial road network from the second example is depicted in Figure 3, and its state after adding new roads is shown in Figure 4.
In the second example, 5 new roads can be added: 2 5, 1 4, 1 6, 3 4, 3 6.