SPCE - Gopu and Combinatorics on Graphs
Little Gopu was playing with graphs. He encountered 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 i.e. 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 separated integers n, m: (1 <= n, m <= 10^5).
Then For each of the next m lines, each line contains two space separated 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??
|
|
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.
|
|
|
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.
|
|
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 |
RSS