Задача. "Сколько вариантов"

Неориентированный граф (возможно, с кратными ребрами) задан списком ребер. Напишите функцию, которая по номерам двух вершин будет возвращать в качестве результата количество способов дойти от одной до другой, пройдя не более чем через одну промежуточную вершину. Например, если в графе есть два ребра (1,2), три ребра (2,3) и одно ребро (1,3), то количество способов дойти из 1 в 3 не более, чем с одной промежуточной вершиной равно 2*3 (через вершину 2) + 1 (прямое ребро) = 7.

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

Дополнительное задание. Подумайте, как лучше хранить граф в памяти, чтобы ответ на запросы вычислялся эффективнее.

Входные данные. Вводятся числа N и M (2≤N≤100, 0≤M≤10000) - количество вершин и ребер графа. Далее идет M пар чисел, задающих ребра. Далее идет количество запросов K (1≤K≤100). Далее идет K пар чисел, задающих запросы (номера вершин графа, между которыми мы считаем способы). Числа в паре различны.

Выходные данные. Для каждого запроса выведите ответ на него.

Примечание. Заметьте, что если в графе есть ребра: (1,2) и (2,1), то фактически это означает, что есть два ребра (1,2) или два ребра (2,1).

Пример

Пример ввода	Пример вывода
5 9 1 2 2 1 2 3 2 3 2 3 3 1 1 4 4 2 4 3 4 1 3 4 1 2 3 1 5	8 4 6 0

Пояснение. Из вершины 1 в 3 можно добраться 8 способами: 6 способов через вершину 2, 1 способ напрямую, и 1 способ через 4. Способ 1-4-2-3 не считаем, так как он прохоит через 2 промежуточных вершины.