Bessie có một đồ thị vô hướng liên thông \(G\) với \(N\) đỉnh được đánh số \(1\ldots N\) và \(M\) cạnh (\(2\le N\le10^2\), \(N-1\le M\le\frac{N^2+N}{2}\)). \(G\) có thể chứa khuyên, tức cạnh nối một đỉnh với chính nó, nhưng không có cạnh song song nối cùng một cặp đầu mút.

Với mỗi \(1\le a\le N\) và \(0\le b\), đặt \(f_G(a,b)\) là hàm Boolean bằng đúng nếu tồn tại một đường đi từ đỉnh \(1\) đến đỉnh \(a\) đi qua đúng \(b\) cạnh, và bằng sai nếu không tồn tại. Nếu một cạnh được đi qua nhiều lần, mỗi lần đều được tính vào số cạnh.

Elsie muốn sao chép Bessie. Cụ thể, cô muốn xây dựng một đồ thị vô hướng \(G'\) sao cho \(f_{G'}(a,b)=f_G(a,b)\) với mọi \(a\) và \(b\).

Hãy đếm số đồ thị \(G'\) phân biệt mà Elsie có thể tạo, lấy modulo \(10^9+7\). Giống \(G\), đồ thị \(G'\) có thể chứa khuyên nhưng không có cạnh song song. Vì vậy, trên tổng số \(N\) đỉnh có nhãn, có \(2^{\frac{N^2+N}{2}}\) đồ thị phân biệt.

Mỗi dữ liệu vào chứa \(T\) bộ test (\(1\le T\le\frac{10^5}{4}\)) cần được giải độc lập. Tổng \(N^2\) trên mọi bộ test không vượt quá \(10^5\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số bộ test.

Dòng đầu của mỗi bộ test chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\) (\(1\le x\le y\le N\)), biểu thị một cạnh giữa \(x\) và \(y\) trong \(G\).

Các bộ test liên tiếp được ngăn cách bằng dòng trống cho dễ đọc.

Dữ liệu ra

Với mỗi bộ test, in trên một dòng mới số đồ thị \(G'\) phân biệt, lấy modulo \(10^9+7\).

Phân nhóm

• Mọi bộ test trong input 3 thỏa mãn \(N\le5\).
• Mọi bộ test trong các input 4-5 thỏa mãn \(M=N-1\).
• Với mọi bộ test trong các input 6-11, nếu không phải \(f_G(x,b)=f_G(y,b)\) với mọi \(b\), thì tồn tại \(b\) sao cho \(f_G(x,b)\) đúng và \(f_G(y,b)\) sai.
• Các bộ test trong các input 12-20 không có ràng buộc bổ sung.

Ví dụ

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

Giải thích ví dụ 1. Trong bộ test đầu tiên, \(G'\) có thể bằng \(G\) hoặc là một trong hai đồ thị sau:

5 4
1 2
1 4
3 4
3 5

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

Giải thích ví dụ 2. Đây là một số bộ test lớn hơn. Cần in đáp án modulo \(10^9+7\). Đáp án của bộ test áp chót là \(2^{45}\pmod{10^9+7}\).

Nguồn

USACO 2021 February Contest, Platinum - Counting Graphs: https://usaco.org/index.php?page=viewproblem2&cpid=1118

Tác giả: Benjamin Qi.