You are given an undirected graph with N vertices and M edges.
It is guaranteed that the graph is simple (no self-loops or multiple edges).
The graph may be unconnected.
Your task is to find how many ways you can add exactly one edges such that the graph becomes connected (meaning that there exists a path between every pair of vertices).Please note that the result graph must be simple, that is you cannot add self-loop or multiple edge to the graph.
The first line of input contains three integers: N, M.
The following M lines of input contain two integers each: u ᵢ and v ᵢ for line i.
For 60% of the test cases, N is less than or equal to 20.
For 40% of the test cases, there are no additional constraints.
Output a single integer representing the number of ways to add exactly one edges such that the graph becomes connected.