Given a connected undirected graph of N edges and M vertices. The task is the find the total number of spanning trees possible in the graph.
Note: A spanning tree is a subset of Graph G, which has all the vertices covered with the minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree.
Example 1:
Input:
N = 6, M = 5
graph = {{0, 3}
{0, 1}
{1, 2}.
{1, 5},
{3, 4}}
Output: 1
Explanation:
Only one spanning tree is possible,i.e. the graph itself.
{{0, 1},
{0, 3},
{1, 2},
{1, 5},
{3, 4}}

Your Task:
You don't need to read input or print anything. Your task is to complete the function countSpanningTrees() which takes two integers N and M and a 2D matrix denoting the connected edges and returns an integers as output.

Expected Time Complexity: O(N^{4})
Expected Auxiliary Space: O(N^{2})

Constraints:
1 <= N <= 10
N - 1 <= M <= N *(N - 1) / 2
0 <= graph[i][0], graph[i][1] <= N - 1

见题面

见题面