Вам дан неориентированных, связный граф из $$$n$$$ вершин и $$$m$$$ ребер. Все вершины $$$u$$$ графа удовлетворяют следующему условию:
- Пусть $$$S_u$$$ это множество вершин принадлежащих длиннейшему простому циклу начинающемуся и заканчивающемуся в $$$u$$$.
- Пусть $$$C_u$$$ это объединение множеств вершин всех простых циклов начинающихся и заканчивающихся в $$$u$$$.
- $$$S_u = C_u$$$.
Вы должны ответить на $$$q$$$ запросов.
Для каждого запроса вам будет дана вершина $$$a$$$ и вершина $$$b$$$. Для всех ребер принадлежащих любому простому пути из $$$a$$$ в $$$b$$$, посчитайте число ребер таких, что если вы удалите их, $$$a$$$ и $$$b$$$ останутся достижимы друг из друга.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min$$$($$$2 \cdot 10^5$$$, $$$(n \cdot (n-1))/2$$$)) — число вершин и ребер графа, соответственно.
Следующие $$$m$$$ строк содержат пары целых чисел $$$u$$$ и $$$v$$$ ($$$1 \le$$$ ($$$u$$$, $$$v$$$) $$$\le n$$$, $$$u \neq v$$$) — описывающие ребра, означающие $$$u$$$ что $$$v$$$ соединены друг с другом.
Гарантируется, что между одной парой вершин проведено не более одного ребра и данный граф связен.
В следующей строке содержится одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.
Затем $$$q$$$ следующих строк содержат запросы. Каждая из них содержит два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le$$$ $$$a$$$, $$$b$$$ $$$\le n$$$).
Для каждого запроса выведите одно целое число — ответ на запрос.
10 11 1 2 2 3 3 4 4 5 5 3 2 7 7 9 9 10 10 6 6 7 1 8 5 1 4 5 10 3 5 2 8 7 10
3 7 3 0 4
13 15 1 2 2 3 3 4 4 1 2 4 3 5 5 6 6 7 6 8 7 9 9 10 8 7 10 11 10 12 10 13 6 9 11 1 5 1 8 5 2 5 12 12 13
0 5 8 5 3 0
Граф в первом примере:
Первый запрос это $$$(1, 4)$$$. Тут всего $$$5$$$ ребер принадлежат любому простому пути из $$$1$$$ в $$$4$$$. Ребра $$$(3, 4), (4, 5), (5, 3)$$$ будут посчитаны как ответ на запрос.
Четвертый запрос $$$(2, 8)$$$. Тут только один простой путь из $$$2$$$ в $$$8$$$, причем ни одно ребро не будет посчитано в ответ.
Пятый запрос $$$(7, 10)$$$. Тут всего $$$4$$$ ребра принадлежат любому простому пути из $$$7$$$ в $$$10$$$, все они будут посчитаны в ответе.
