## 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

### 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:
44 21 23 45 31 23 44 53 31 22 33 17 51 23 44 53 56 7 ```
```Output:
46-184```