Đếm Đồ Thị

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một đồ thị vô hướng liên thông $G$ có $N$ đỉnh được đánh số từ $1$ đến $N$ và $M$ cạnh. Đồ thị có thể có khuyên (cạnh nối một đỉnh với chính nó) nhưng không có cạnh song song.

Định nghĩa hàm boolean $f_{G} (a, b)$ bằng true nếu tồn tại đường đi từ đỉnh $1$ đến đỉnh $a$ đi qua đúng $b$ cạnh (mỗi cạnh được tính mỗi lần đi qua), và false nếu không tồn tại.

Đếm số đồ thị vô hướng $G^{'}$ (có thể có khuyên, không có cạnh song song, trên $N$ đỉnh được đánh nhãn) thỏa mãn $f_{G^{'}} (a, b) = f_{G} (a, b)$ với mọi $a$ và $b$ . Kết quả tính theo modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $T$ — số lượng test case.

Mỗi test case bắt đầu bằng một dòng chứa hai số nguyên $N$ và $M$ . Tiếp theo là $M$ dòng, mỗi dòng chứa hai số nguyên $x$ và $y$ ( $1 \leq x \leq y \leq N$ ) mô tả một cạnh trong $G$ .

Các test case liên tiếp được phân cách bởi dòng trống.

Dữ liệu ra

Với mỗi test case, in ra một số nguyên duy nhất là số đồ thị $G^{'}$ thỏa mãn, modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq T \leq \frac{10^{5}}{4}$
$2 \leq N \leq 10^{2}$
$N - 1 \leq M \leq \frac{N^{2} + N}{2}$
Tổng $N^{2}$ của tất cả các test case không vượt quá $10^{5}$

Ví dụ

Input	Output	Giải thích
1 5 4 1 2 2 3 1 4 3 5	3	$G^{'}$ có thể là $G$ ban đầu, hoặc đồ thị với các cạnh {1-2, 1-4, 3-4, 3-5}, hoặc đồ thị với các cạnh {1-2, 2-3, 1-4, 3-4, 3-5}.
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

Bình luận

Không có bình luận tại thời điểm này.