Задача: Считаем графы
У Маши есть связный ненаправленный граф G с N вершинами, помеченными 1…N и M ребрами (\(1 \leq N \leq10^2\), \(N-1 \leq M \leq \frac {N^2+N}{2}\)). G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть \(f_G(a,b)\) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для \(1 \leq a \leq N\) и \(0 \leq b\), и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ.
Даша хочет повторить за Машей. В частности, она хочет сконструировать ненаправленный граф G′ такой, что \(f_{G'}(a,b)=f_G(a,b)\) для всех a и b.
Посчитайте количество различных графов G′, которые Даша может создать, по модулю \(10^9+7\). Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего \(2^{ \frac {N^2+N} {2}}\) различных графов на N вершинах).
Каждый ввод содержит T (\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма \(N^2\) по всем тестам не превысит \(10^5\).
Входные данные
Первая строка ввода содержит T, количество тестов.
Первая строка каждого теста содержит два целых числа N и M.
Следующие M строк каждого теста содержат два целых числа x и y (\(1 \leq x \leq y \leq N\)), обозначающих ребро между x и y в G.
Тесты разделены пустой строкой для читабельности.
Выходные данные
Для каждого теста выведите количество различных G′ по модулю \(10^9+7\) на отдельной строке.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
1
5 4
1 2
2 3
1 4
3 5 |
3 |
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 |
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 |
Это пример более крупного теста.
Обязательно выводите ответ по модулю \(10^9+7\).
Обратите внимание, что ответ для предпоследнего теста - \(2^{45}\ \ (mod\ 10^9 + 7)\). |
Ваш ответ: