Problem Description

Bessie has a connected undirected graph $G$. $G$ has $N$ vertices numbered $1 \ldots N$ and $M$ edges ($1 \le N \le 10^2$, $N-1 \le M \le \frac{N^2+N}{2}$). $G$ may contain self-loops (an edge from a vertex to itself), but it does not contain multiple edges (multiple edges connecting the same pair of vertices).

Let $f_G(a,b)$ be a boolean function. For each $1 \le a \le N$ and $0 \le b$, the function is true if there exists a path from vertex $1$ to vertex $a$ that uses exactly $b$ edges, and false otherwise. If an edge is traversed multiple times, it is counted that many times.

Elsie wants to copy Bessie. Specifically, she wants to construct an undirected graph $G'$ such that for all $a$ and $b$, we have $f_{G'}(a,b)=f_G(a,b)$.

Your task is to compute the number of graphs $G'$ that Elsie can construct, modulo $10^9+7$. Just like $G$, $G'$ may contain self-loops but cannot contain multiple edges (this means that for $N$ labeled vertices there are $2^{\frac{N^2+N}{2}}$ different graphs in total).

Each input contains $T$ ($1 \le T \le \frac{10^5}{4}$) independent test cases. It is guaranteed that the sum of $N^2$ over all test cases does not exceed $10^5$.

Input Format

The first line of input contains $T$, the number of test cases.

The first line of each test case contains integers $N$ and $M$.

Each of the next $M$ lines of the test case contains two integers $x$ and $y$ ($1 \le x \le y \le N$), meaning that there is an edge connecting $x$ and $y$ in $G$.

For readability, adjacent test cases are separated by a blank line.

Output Format

For each test case, output one line: the number of different graphs $G'$, modulo $10^9+7$.

1

5 4
1 2
2 3
1 4
3 5

3

7

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

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

5 7
1 2
1 3
1 5
2 4
3 3
3 4
4 5

6 6
1 2
2 3
3 4
4 5
5 6
6 6

6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

22 28
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 8
3 9
8 10
10 11
10 12
10 13
10 14
11 15
12 16
13 17
14 18
9 15
9 16
9 17
9 18
15 19
19 20
15 20
16 21
21 22
16 22

45
35
11
1
15
371842544
256838540

Hint

Explanation for Sample 1:

In the first test case, $G'$ can be equal to $G$, or one of the following two graphs:

5 4
1 2
1 4
3 4
3 5

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

Explanation for Sample 2:

There are some larger test cases. Make sure your answer is taken modulo $10^9+7$. Note that the answer for the second-to-last test case is $2^{45}\pmod{10^9+7}$.

Test Point Properties:

• For an additional $5\%$ of the testdata, $N \le 5$.
• For an additional $10\%$ of the testdata, $M = N-1$.
• For an additional $30\%$ of the testdata, if it is not true that for all $b$ we have $f_G(x,b)=f_G(y,b)$, then there exists $b$ such that $f_G(x,b)$ is true and $f_G(y,b)$ is false.
• For an additional $45\%$ of the testdata, there are no additional constraints.

Problem by: Benjamin Qi.

Translated by ChatGPT 5