题目描述

现代社会，路是必不可少的。

共有 $n$ 个城镇，$m$ 条双向道路，任意两个城镇之间都有路径相连（即原图是连通的），而且往往不止一条路径。

但有些路年久失修，走着很不舒服。

按理说“条条大路通罗马”，大不了绕行其他路呗——可是小撸却发现：从 $a$ 城到 $b$ 城不管怎么走，总有一些逃不掉的必经之路。

他想请你计算一下，从 $a$ 到 $b$ 的所有路径中，有几条道路是逃不掉的（即无论走哪条从 $a$ 到 $b$ 的路径，都会经过的边的数量）？

输入格式

第一行两个整数 $n$ 和 $m$，用空格隔开。

接下来 $m$ 行，每行两个整数 $x$ 和 $y$，用空格隔开，表示 $x$ 城和 $y$ 城之间有一条双向道路。

第 $m+2$ 行是一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个整数 $a$ 和 $b$，用空格隔开，表示一次询问。

输出格式

对于每次询问，输出一个整数，表示 $a$ 城到 $b$ 城必须经过的道路的数量。

每个输出占一行。

样例

输入样例：

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

输出样例：

0
1

样例解释

• 对于询问 $1$ 到 $4$：可以走 $1 \to 2 \to 4$ 或 $1 \to 3 \to 4$，没有一条边是两条路径都经过的，所以答案为 $0$。
• 对于询问 $2$ 到 $5$：无论怎么走，都必须经过 $4 \to 5$ 这条边，所以答案为 $1$。

数据范围

• $1 \leq n \leq 10^5$
• $1 \leq m \leq 2 \times 10^5$
• $1 \leq q \leq 10^5$
• $1 \leq x, y, a, b \leq n$，且 $x \neq y, a \neq b$
• 任意两个城镇之间都有路径相连（原图连通）
• 同一条道路不会输入两次
• 对于任意的道路，两端的城市编号之差不超过 $10^4$

时空限制

• 时间限制：2 秒
• 空间限制：512 MB