Reconstruction#3512
In a certain country, there are exactly cities and roads connecting them. The road network in this country is structured as follows:
There is at most one road between any two cities.
No road connects a city to itself.
Following a change in government, the new administration has decided to implement a series of reforms, including changes to the road system. The reform involves two main actions:
Demolish one of the existing roads.
Construct a new road that did not previously exist, ensuring it does not connect a city to itself.
Additionally, to enhance economic connectivity between cities, the government wants to ensure that after the road reform, it is possible to travel between any pair of cities. It is not guaranteed that this condition was satisfied before the reform.
The government is now considering how many different ways the reform can be executed. Your task is to help them determine this number.
The first line contains two integers and (1 \leq n \leq 100\,000, 0 \leq m \leq 200\,000). The following lines each contain two integers a_i and b_i (1 \leq a_i, b_i \leq n, a_i \neq b_i), representing the cities connected by the -th road.
Output a single integer, the number of ways to execute the reform.
Example 1