У Беси есть связный ненаправленный граф G с n вершинами, помеченными 1..n и m ребрами. G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть fG(a, b) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для 1 ≤ a ≤ n и 0 ≤ b, и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ.
Эльза хочет копировать Беси. В частности, она хочет сконструировать ненаправленный граф G′ такой, что fG′(a, b) = fG(a, b) для всех a и b.
Ваша задача посчитать количество различных графов G′, которые Эльза может создать, по модулю 10^9
+ 7. Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего 2 ^ ((n^2
+ n) / 2) различных графов на n вершинах).
Каждый вход содержит t тестов, которые должны решаться независимо. Гарантируется, что сумма n^2
по всем тестам не превысит 10^5
.
Первая строка ввода содержит количество тестов t (1 ≤ t ≤ 10^5
/ 4).
Первая строка каждого теста содержит два целых числа n и m (1 ≤ n ≤ 10^2
, n − 1 ≤ m ≤ (n^2
+ n) / 2.
Следующие m строк каждого теста содержат два целых числа x и y (1 ≤ x ≤ y ≤ n), обозначающих ребро между x и y в G.
Последовательные тесты разделены пустой строй для читабельности.
Для каждого теста выведите количество различных G′ по модулю 10^9
+ 7 в новой строке.
В этом тесте G′ может быть равен G или одному из двух следующих графов: