Biconnected

People are weak. Relationship between people like friendship or love is weak too. But a group of persons can have strong relationship, umm, 2-edge-connected relationship.

Suppose there are n persons. If two persons, A and B, are in a relationship, then we add an un-directional edge between them. In this way we can have a relationship graph, which is an un-directional graph without self-loops or multiple edges. If this graph is 2-edge-connected, then we say these persons have a strong relationship.

Now we have a group of persons without relationship between any two of them. And some pair of persons even hate each other. You will introduce some pairs of persons to know each other and set up a relationship between them to make the group of persons have a strong relationship. But notice that you can't set up a relationship between a pair of persons who hate each other. How many ways you can do that? (Two ways are different if there exist a pair of persons which have relationship in one way but not in another way).

output the answer modulo 1e9+7

The first line contains an integer T, denoting the number of the test cases.

For each test case, the first line contains 2 integers n and m, denoting the number of persons in the group and the number of pairs of persons who hate each other. Then m lines follow, each line containing 2 integers A and B, denoting that A and B hate each other.

T<=5, 2<=n<=10, 0<=m<=n*(n-1)/2. The persons are indexed from 1.

For each test case, output the answer in a line.

3
5 0
10 0
5 2
1 2
2 3

253
466997276
18

A 2-edge-connected graph is a graph which is connected and if you remove an edge from it, it is still connected.

Note that n>=2, so we can ignore the issue that whether a single vertex is 2-edge-connected or not :).

2014 ACM/ICPC Asia Regional Anshan Online