E. Кактус
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Связный неориентированный граф называется вершинным кактусом, если каждая вершина этого графа принадлежит не более чем одному простому циклу.

Простым циклом в неориентированном графе назовем последовательность различных вершин v1, v2, ..., vt (t > 2) такую, что для любого i (1 ≤ i < t) существует ребро между вершинами vi и vi + 1, а также существует ребро между вершинами v1 и vt.

Простым путем в неориентированном графе назовем последовательность не обязательно различных вершин v1, v2, ..., vt (t > 0) такую, что для любого i (1 ≤ i < t) существует ребро между вершинами vi и vi + 1, причем каждое ребро встречается не более одного раза. Будем говорить, что простой путь v1, v2, ..., vt начинается в вершине v1 и заканчивается в вершине vt.

Вам задан граф, состоящий из n вершин и m ребер, который является вершинным кактусом. Также есть список из k пар интересных вершин xi, yi, для которых Вы захотели узнать следующую информацию — сколько различных простых путей начинается в вершине xi и заканчивается в вершине yi. Два простых пути будем считать различными, если различаются множества ребер, которые в них входят.

Для каждой пары интересных вершин посчитайте количество различных простых путей между ними. Поскольку это количество может быть достаточно большим, требуется посчитать остаток от деления этого числа на 1000000007 (109 + 7).

Входные данные

В первой строке через пробел записаны два целых числа n, m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105) — количество вершин и ребер в графе соответственно. В следующих m строках задано описание ребер: в i-той строке через пробел записаны два целых числа ai, bi (1 ≤ ai, bi ≤ n) — номера вершин, которые соединяет i-тое ребро.

Во следующей строке записано единственное целое число k (1 ≤ k ≤ 105) — количество пар интересных вершин. В следующих k строках задан список пар интересных вершин: в i-ой строке через пробел записаны два целых числа xi, yi (1 ≤ xi, yi ≤ n; xi ≠ yi) — номера интересных вершин в i-ой паре.

Гарантируется, что заданный граф является вершинным кактусом. Гарантируется, что в графе отсутствуют петли и кратные ребра. Считайте, что вершины графа некоторым образом пронумерованы от 1 до n.

Выходные данные

Выведите k строк: в i-ой строке выведите единственное число — остаток от деления количества различных простых путей, начинающихся в xi и заканчивающихся в yi, на 1000000007 (109 + 7).

Примеры
Входные данные
10 11
1 2
2 3
3 4
1 4
3 5
5 6
8 6
8 7
7 6
7 9
9 10
6
1 2
3 5
6 9
9 2
9 3
9 10
Выходные данные
2
2
2
4
4
1