Counting Graphs#11218
Bessie has a connected, undirected graph with vertices labeled and edges. may contain self-loops (edges from nodes back to themselves), but no parallel edges (multiple edges connecting the same endpoints).
Let f_G(a, b) be a boolean function that evaluates to true if there exists a path from vertex to vertex that traverses exactly edges for each 1 \leq a \leq n and 0 \leq b, and false otherwise. If an edge is traversed multiple times, it is included that many times in the count.
Elsie wants to copy Bessie. In particular, she wants to construct an undirected graph G' such that f_{G'}(a, b) = f_G(a, b) for all and .
Your job is to count the number of distinct graphs G' that Elsie may create, modulo 10^9 + 7. As with , G' may contain self-loops but no parallel edges (meaning that there are 2^{(n^2 + n) / 2} distinct graphs on labeled vertices in total).
Each input contains test cases that should be solved independently. It is guaranteed that the sum of n^2 over all test cases does not exceed 10^5.
The first line contains (1 \leq t \leq 10^5 / 4), the number of test cases.
The first line of each test case contains the integers and (1 \leq n \leq 10^2, n - 1 \leq m \leq (n^2 + n) / 2).
The next lines of each test case each contain two integers and (1 \leq x \leq y \leq n), denoting that there exists an edge between and in .
Consecutive test cases are separated by newlines for readability.
For each test case, the number of distinct G' modulo 10^9 + 7 on a new line.
In the first test case, G' could equal or one of the two following graphs:
"' 5 4 1 2 1 4 3 4 3 5 5 5 1 2 2 3 1 4 3 4 3 5 "'
Example 1