Graph Replication Count

Bessie has a connected undirected graph \(G\). The graph \(G\) has \(N\) vertices numbered \(1,2,\dots,N\) and \(M\) edges, where \(1 \le N \le 10^2\) and \(N-1 \le M \le \frac{N^2+N}{2}\). The graph may contain self-loops (an edge connecting a vertex to itself) but no multiple edges (i.e. at most one edge between any unordered pair of vertices).

Define a Boolean function \(f_G(a,b)\) for every vertex \(1 \le a \le N\) and every nonnegative integer \(b\). We have \(f_G(a,b)=\textbf{true}\) if and only if there exists a walk (where edges may be repeated) from vertex \(1\) to vertex \(a\) that uses exactly \(b\) edges; otherwise, \(f_G(a,b)=\textbf{false}\). (Note that if an edge is used multiple times in a walk, it is counted correspondingly.)

Elsie wishes to replicate Bessie by constructing another undirected graph \(G'\) on the same set of \(N\) labeled vertices. The graph \(G'\) is allowed to contain self-loops but not multiple edges, and it must satisfy \[ f_{G'}(a,b)= f_G(a,b) \quad\text{for every } 1\le a \le N \text{ and } b \ge 0. \] Your task is to compute, modulo \(10^9+7\), the number of graphs \(G'\) that Elsie can construct which satisfy the above condition. (Note that there are exactly \(2^{\frac{N^2+N}{2}}\) different undirected graphs on \(N\) labeled vertices when self-loops are allowed but multiple edges are not.)

Observation: If we compute the shortest distance \(d(a)\) from vertex \(1\) to each vertex \(a\) in \(G\), then the set of integers \(b\) for which \(f_G(a,b)\) is true is determined by two cases:

• If \(G\) is bipartite then every walk from \(1\) to \(a\) has the same parity as \(d(a)\) (because any detour adds an even number of edges). In this case, \(f_G(a,b)=\textbf{true}\) if and only if \(b\ge d(a)\) and \(b\equiv d(a)\, (\bmod\, 2)\).
• If \(G\) is non-bipartite then there exists some odd cycle reachable from \(1\), so for every vertex \(a\) we have \(f_G(a,b)=\textbf{true}\) for all \(b\ge d(a)\).

Thus, the function \(f_G(\cdot,\cdot)\) is completely determined by the shortest distances \(d(a)\) and the bipartiteness of \(G\). In any candidate graph \(G'\) with the same function \(f_{G'}(a,b)=f_G(a,b)\), the shortest distances from vertex \(1\) must remain unchanged. Moreover, if \(G\) is bipartite, then the bipartite partition given by the parities of \(d(a)\) must be maintained in \(G'\); that is, no extra edge connecting two vertices of the same parity (or any self-loop) is permitted. On the other hand, if \(G\) is non-bipartite, then at least one edge that makes the graph non-bipartite (such as a self-loop or an edge connecting vertices at the same distance) must appear in \(G'\).

One may partition the vertices according to their distances from \(1\): let \(L_k\) be the set of vertices with \(d(a)=k\) for \(k=0,1,\dots, L\) (with \(L\) being the maximum distance). For every vertex in \(L_k\) for \(k\ge1\), there must be at least one edge connecting it to some vertex in \(L_{k-1}\). Thus, the choices for edges between adjacent levels contribute a factor of \(\prod_{k=1}^{L} \left(2^{|L_{k-1}|} - 1\right)^{|L_k|}\) to the answer. Additionally, edges within the same level and self-loops can be chosen arbitrarily if and only if \(G\) is non-bipartite – but at least one such edge must be chosen to ensure non-bipartiteness.

Your task is to compute the total number of valid graphs \(G'\) modulo \(10^9+7\) given these constraints.

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 10^5/4\)), representing the number of test cases. Then \(T\) test cases follow. Each test case begins with a line containing two integers \(N\) and \(M\) (with \(1 \le N \le 10^2\) and \(N-1 \le M \le \frac{N^2+N}{2}\)). It is guaranteed that the sum of \(N^2\) over all test cases does not exceed \(10^5\). Following this, there are \(M\) lines, each containing two integers \(u\) and \(v\) (\(1 \le u,v \le N\)) representing an undirected edge. Note that self-loops are allowed but there are no multiple edges.

outputFormat

For each test case, output one integer – the number of graphs \(G'\) satisfying \(f_{G'}(a,b)=f_G(a,b)\) for all vertices \(a\) and nonnegative integers \(b\), taken modulo \(10^9+7\).

The output for different test cases should be printed on separate lines.

sample

3
3 2
1 2
2 3
3 3
1 2
2 3
1 3
4 3
1 2
2 3
3 4

1
45
1