SPCE - Gopu and Combinatorics on Graphs

no tags 

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: 2016-05-02 21:55:36

awesome

Bhavik: 2014-03-08 19:55:53

@praveen123: can you kindly chk my id:11211793 and tell where my code fails??
also for n=1 ans should be -1 right?
thank you

Piyush Kumar: 2014-01-30 12:58:40

@Mitch : I hope to find it eventually :)

Mitch Schwartz: 2014-01-30 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 co-exist in the classical section. @Piyush Kumar, it seems likely that at least two people created this problem independently.

Last edit: 2014-01-30 04:24:36
Piyush Kumar: 2014-01-30 01:23:44

Nicest graph theory problem I have solved in a while. btw, who came up with this?

Mitch Schwartz: 2014-01-14 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 k-1 edges must be added, so try every way of choosing k-1 new edges and count how many of those ways make the graph connected. Then review the math.

Last edit: 2014-01-14 17:29:02
Bhavik: 2014-01-14 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.
plz correct me if i am interpreting wrong..

@Mitch: thanks for your reply. I will look as you mentioned..

Last edit: 2014-01-14 16:01:33
Mitch Schwartz: 2014-01-14 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.

Edit: Thanks for your understanding.

Last edit: 2014-01-14 14:12:01
anurag garg: 2014-01-14 19:45:21

@ mitch sir I have removed my comment...

Last edit: 2014-01-14 10:13:00

Added by:praveen123
Date:2013-12-23
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge