Сессионная школа: Обход в глубину (более сложные задачи)

Вам дан неориентированный граф с \(n\) вершинами и \(m\) ребрами, не содержащий петель и кратных ребер. Так же вам дано несколько пар вершин \((a_i, b_i)\). Для каждой пары требуется найти количество вершин \(c\), таких, что существует путь из \(a_i\) в \(b_i\), проходящий через вершину \(c\).

Путь из \(a\) в \(b\) -- это последовательность вершин, начинающаяся в \(a\) и заканчивающаяся в \(b\), такая, что каждые две соседние вершины этой последовательности соединены ребром. Обратите внимание, что путь может проходить по одной и той же вершине более одного раза.

В первой строке через пробел записаны два целых числа \(n\) и \(m\) (\(1 \le n \le 100; 0 \le m \le {n \cdot (n-1) \over 2}\)) --- количество вершин и ребер графа. В следующих \(m\) строчках записано по два целых числа \(u\) и \(v\) (\(1 \le u,v \le n; u \neq v\)) --- номера вершин, которые соединяет описываемое ребро.

В следующей строке записано единственное целое число \(q\) (\(1 \le q \le 5000\)) --- количество пар \((a_i, b_i)\). В следующих \(q\) строках описываются пары. В \(i\)-й из этих строк через пробел записаны целые числа \(a_i\) и \(b_i\) (\(a_i \neq b_i\); \(1 \le a_i, b_i \le n\)).

Для каждой описанной пары выведите на отдельной строке единственное число --- количество вершин \(c\), таких, что существует путь из \(a_i\) в \(b_i\), проходящий через \(c\).

4 3
1 2
2 3
3 4
2
1 2
1 3

4
4