[USACO21FEB] Counting Graphs P

题目描述

Bessie 有一个连通无向图 $G$。$G$ 有 $N$ 个编号为 $1\ldots N$ 的结点,以及 $M$ 条边($1\le N\le 10^2, N-1\le M\le \frac{N^2+N}{2}$)。$G$ 有可能包含自环(一个结点连到自身的边),但不包含重边(连接同一对结点的多条边)。 令 $f_G(a,b)$ 为一个布尔函数,对于每一个 $1\le a\le N$ 和 $0\le b$,如果存在一条从结点 $1$ 到结点 $a$ 的路径恰好经过了 $b$ 条边,则函数值为真,否则为假。如果一条边被经过了多次,则这条边会被计算相应的次数。 Elsie 想要复制 Bessie。具体地说,她想要构造一个无向图 $G'$,使得对于所有的 $a$ 和 $b$,均有 $f_{G'}(a,b)=f_G(a,b)$。 你的工作是计算 Elsie 可以构造的图 $G'$ 的数量,对 $10^9+7$ 取模。与 $G$ 一样,$G'$ 可以包含自环而不能包含重边(这意味着对于 $N$ 个有标号结点共有 $2^{\frac{N^2+N}{2}}$ 个不同的图)。 每个输入包含 $T$($1\le T\le \frac{10^5}{4}$)组独立的测试用例。保证所有测试用例中的 $N^2$ 之和不超过 $10^5$。

输入输出格式

输入格式


输入的第一行包含 $T$,为测试用例的数量。 每个测试用例的第一行包含整数 $N$ 和 $M$。 每个测试用例的以下 $M$ 行每行包含两个整数 $x$ 和 $y$($1\le x\le y\le N$),表示 $G$ 中存在一条连接 $x$ 与 $y$ 的边。 为提高可读性,相邻的测试用例之间用一个空行隔开。

输出格式


对每个测试用例,输出一行,为不同的 $G'$ 的数量,对 $10^9+7$ 取模。

输入输出样例

输入样例 #1

1

5 4
1 2
2 3
1 4
3 5

输出样例 #1

3

输入样例 #2

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

输出样例 #2

45
35
11
1
15
371842544
256838540

说明

#### 样例 1 解释: 在第一个测试用例中,$G'$ 可以等于 $G$,或以下两个图之一: ``` 5 4 1 2 1 4 3 4 3 5 ``` ``` 5 5 1 2 2 3 1 4 3 4 3 5 ``` #### 样例 2 解释: 有一些较大的测试用例。确保你的答案对 $10^9+7$ 取模。注意倒数第二个测试用例的答案为 $2^{45}\pmod{10^9+7}$。 #### 测试点性质: - 对于另外 $5\%$ 的数据,满足 $N\le 5$。 - 对于另外 $10\%$ 的数据,满足 $M=N-1$。 - 对于另外 $30\%$ 的数据,如果并非对于所有的 $b$ 均有 $f_G(x,b)=f_G(y,b)$,则存在 $b$ 使得 $f_G(x,b)$ 为真且 $f_G(y,b)$ 为假。 - 对于另外 $45\%$ 的数据,没有额外限制。 供题:Benjamin Qi