SPCE  Gopu and Combinatorics on Graphs
Little Gopu was playing with graphs. He encoutered following problem while playing.
Given a graph G with n vertices and m edges. Let us say it has k connected components. Find out how many numbers of ways you can add k  1 edges to make the graph connected. Note that the new edge you are going to add should not be a repeated edge ie. if you are going to connect u, v then there should not be an edge between u, v already in the graph. Output the answer modulo 10^9 + 7.
If the graph is already connected, Output 1
Help Gopu with this task.
Input
First line contains T : number of test cases. (1 <= T <= 20)
For each test case, First line contains two space seperated integers n, m: (1 <= n, m <= 10^5).
Then For each of the next m lines, each line contains two space seperated integers u and v denoting that u and v are connected to each other. (1 <= u, v <= n and u != v)
Output
For each test case, output the answer as required.
Example
Input: 4
4 2
1 2
3 4
5 3
1 2
3 4
4 5
3 3
1 2
2 3
3 1
7 5
1 2
3 4
4 5
3 5
6 7
Output: 4
6
1
84
hide comments
Archit Jain:
20160502 21:55:36
awesome 

Bhavik:
20140308 19:55:53
@praveen123: can you kindly chk my id:11211793 and tell where my code fails??


Piyush Kumar:
20140130 12:58:40
@Mitch : I hope to find it eventually :) 

Mitch Schwartz:
20140130 02:32:27
This problem actually already exists on SPOJ in a somewhat different form (I knew this from the beginning, and just slightly modified some old code to get AC here), but it would be kind of a spoiler to say which one, as the connection might not be obvious. :p If you know which one it is, please don't say here (or there); I think it's ok for both problems to coexist in the classical section. @Piyush Kumar, it seems likely that at least two people created this problem independently. Last edit: 20140130 04:24:36 

Piyush Kumar:
20140130 01:23:44
Nicest graph theory problem I have solved in a while. btw, who came up with this? 

Mitch Schwartz:
20140114 19:45:21
@Bhavik: I would guess a math error is more likely than an interpretation error. You could check against this slower way: you know that k1 edges must be added, so try every way of choosing k1 new edges and count how many of those ways make the graph connected. Then review the math. Last edit: 20140114 17:29:02 

Bhavik:
20140114 19:45:21
@Mitch: sir can you plz explain how ans for the last case is 84. there will be 3 components and no of possible ways to make graph connected comes out to be 12.


Mitch Schwartz:
20140114 19:45:21
@anurag garg: If you think there is something unclear in the statement, specify it. Right now, all you are doing is encouraging people to leave spoilers.


anurag garg:
20140114 19:45:21
@ mitch sir I have removed my comment... Last edit: 20140114 10:13:00 
Added by:  praveen123 
Date:  20131223 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IITK ACA CSE online judge 