Placeholder

#5775

Counting Graphs 1초 512MB

문제

Bessie has a connected, undirected graph GG with NN vertices labeled 1…N1…N and MM edges (2≤N≤102,N−1≤M≤N2+N2(2≤N≤102,N−1≤M≤N2+N2). GG may contain self-loops (edges from nodes back to themselves), but no parallel edges (multiple edges connecting the same endpoints).

Let fG(a,b)f_G(a,b) be a boolean function that evaluates to true if there exists a path from vertex 11 to vertex aa that traverses exactly bb edges for each 1≤a≤N1≤a≤N and 0≤b0≤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′G′ such that fG′(a,b)=fG(a,b)f_G′(a,b)=f_G(a,b) for all aa and bb.

Your job is to count the number of distinct graphs G′G′ that Elsie may create, modulo 109+710^9+7. As with GG, G′G′ may contain self-loops but no parallel edges (meaning that there are 2^((N^2+N)/2) distinct graphs on NN labeled vertices in total).

Each input contains TT (1≤T≤1≤T≤105/410^5/4) test cases that should be solved independently. It is guaranteed that the sum of N2N^2

over all test cases does not exceed 10510^5.


입력

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

The first line of each test case contains the integers NN and MM.

The next MM lines of each test case each contain two integers xx and yy (1≤x≤y≤N(1≤x≤y≤N), denoting that there exists an edge between xx and yy in GG.

Consecutive test cases are separated by newlines for readability.


출력

For each test case, the number of distinct G′G′ modulo 109+710^9+7 on a new line.


예제1

입력
1

5 4
1 2
2 3
1 4
3 5
출력
3

In the first test case, G′G′ could equal GG 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

예제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
출력
45
35
11
1
15
371842544
256838540

These are some larger test cases. Make sure to output the answer modulo 109+710^9+7. Note that the answer for the second-to-last test case is 2^45(mod109+710^9+7)

.


출처

USACO 2021 Febuary Platinum


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.