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