CF178B3.Greedy Merchants

In ABBYY a wonderful Smart Beaver lives. This time, he began to study history. When he read about the Roman Empire, he became interested in the life of merchants.

The Roman Empire consisted of n cities numbered from 1 to n. It also had m bidirectional roads numbered from 1 to m. Each road connected two different cities. Any two cities were connected by no more than one road.

We say that there is a path between cities _c_1 and _c_2 if there exists a finite sequence of cities _t_1, _t_2, ..., t__p (p ≥ 1) such that:

• _t_1 = _c_1
• t__p = _c_2
• for any i (1 ≤ i < p), cities t__i and t__i + 1 are connected by a road

We know that there existed a path between any two cities in the Roman Empire.

In the Empire k merchants lived numbered from 1 to k. For each merchant we know a pair of numbers s__i and l__i, where s__i is the number of the city where this merchant's warehouse is, and l__i is the number of the city where his shop is. The shop and the warehouse could be located in different cities, so the merchants had to deliver goods from the warehouse to the shop.

Let's call a road important for the merchant if its destruction threatens to ruin the merchant, that is, without this road there is no path from the merchant's warehouse to his shop. Merchants in the Roman Empire are very greedy, so each merchant pays a tax (1 dinar) only for those roads which are important for him. In other words, each merchant pays d__i dinars of tax, where d__i (d__i ≥ 0) is the number of roads important for the i-th merchant.

The tax collection day came in the Empire. The Smart Beaver from ABBYY is very curious by nature, so he decided to count how many dinars each merchant had paid that day. And now he needs your help.

在 ABBYY，住着一只奇妙的“聪明海狸”。这一次，他开始学习历史。当他读到罗马帝国时，对商人的生活产生了兴趣。

罗马帝国由 $n$ 座城市组成，编号从 $1$ 到 $n$；同时还拥有 $m$ 条双向道路，编号从 $1$ 到 $m$。每条道路连接两座不同的城市，且任意两座城市之间至多只有一条道路相连。

我们称城市 $c_1$ 与 $c_2$ 之间存在路径，当且仅当存在一个有限的城市序列 $t_1,\ t_2,\ \dots,\ t_p$（其中 $p\geq 1$），满足：

• $t_1 = c_1$
• $t_p = c_2$
• 对任意 $i$（$1 \leq i < p$），城市 $t_i$ 与 $t_{i+1}$ 由一条道路直接相连

已知：在罗马帝国中，任意两座城市之间均存在路径。

帝国中共有 $k$ 位商人，编号从 $1$ 到 $k$。对第 $i$ 位商人，我们已知一对数 $s_i$ 和 $l_i$，其中 $s_i$ 表示该商人仓库所在的城市编号，$l_i$ 表示其店铺所在的城市编号。仓库与店铺可能位于不同城市，因此商人需将货物从仓库运送到店铺。

我们称某条道路对第 $i$ 位商人是重要的，如果该道路被毁将导致该商人破产——即，移除该道路后，其仓库所在城市到店铺所在城市之间不再存在路径。罗马帝国的商人极其贪婪，因此每位商人仅对那些对其自身重要的道路缴纳税款（每条重要道路缴税 1 第纳尔）。换言之，第 $i$ 位商人当日缴纳的税款为 $d_i$ 第纳尔，其中 $d_i$（$d_i \geq 0$）表示对第 $i$ 位商人而言重要的道路数量。

帝国的征税日到了。ABBYY 的聪明海狸天性好奇，决定统计当天每位商人各自缴纳了多少第纳尔。现在，他需要你的帮助。

The first input line contains two integers n and m, separated by a space, n is the number of cities, and m is the number of roads in the empire.

The following m lines contain pairs of integers a__i, b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i), separated by a space — the numbers of cities connected by the i-th road. It is guaranteed that any two cities are connected by no more than one road and that there exists a path between any two cities in the Roman Empire.

The next line contains a single integer k — the number of merchants in the empire.

The following k lines contain pairs of integers s__i, l__i (1 ≤ s__i, l__i ≤ n), separated by a space, — s__i is the number of the city in which the warehouse of the i-th merchant is located, and l__i is the number of the city in which the shop of the i-th merchant is located.

The input limitations for getting 20 points are:

• 1 ≤ n ≤ 200
• 1 ≤ m ≤ 200
• 1 ≤ k ≤ 200

The input limitations for getting 50 points are:

• 1 ≤ n ≤ 2000
• 1 ≤ m ≤ 2000
• 1 ≤ k ≤ 2000

The input limitations for getting 100 points are:

• 1 ≤ n ≤ 105
• 1 ≤ m ≤ 105
• 1 ≤ k ≤ 105

第一行输入包含两个整数 $n$ 和 $m$，以空格分隔；其中 $n$ 表示城市的数量，$m$ 表示帝国中道路的数量。

接下来的 $m$ 行每行包含一对整数 $a_i$, $b_i$（满足 $1 \le a_i, b_i \le n$ 且 $a_i \ne b_i$），以空格分隔——表示第 $i$ 条道路所连接的两座城市的编号。保证任意两座城市之间至多只有一条道路，并且罗马帝国内任意两座城市之间均存在路径。

下一行包含一个整数 $k$——表示帝国中商人的数量。

接下来的 $k$ 行每行包含一对整数 $s_i$, $l_i$（满足 $1 \le s_i, l_i \le n$），以空格分隔——其中 $s_i$ 表示第 $i$ 位商人仓库所在的城市编号，$l_i$ 表示第 $i$ 位商人店铺所在的城市编号。

获取 20 分的输入限制为：

• $1 \le n \le 200$
• $1 \le m \le 200$
• $1 \le k \le 200$

获取 50 分的输入限制为：

• $1 \le n \le 2000$
• $1 \le m \le 2000$
• $1 \le k \le 2000$

获取 100 分的输入限制为：

• $1 \le n \le 10^5$
• $1 \le m \le 10^5$
• $1 \le k \le 10^5$

Print exactly k lines, the i-th line should contain a single integer d__i — the number of dinars that the i-th merchant paid.

恰好输出 k 行，其中第 i 行应包含一个整数 d__i —— 即第 i 个商人所支付的第纳尔数。

The given sample is illustrated in the figure below.

Let's describe the result for the first merchant. The merchant's warehouse is located in city 1 and his shop is in city 5. Let us note that if either road, (1, 2) or (2, 3) is destroyed, there won't be any path between cities 1 and 5 anymore. If any other road is destroyed, the path will be preserved. That's why for the given merchant the answer is 2.

给出的样例在下图中展示。

我们来分析第一位商家的结果。该商家的仓库位于城市 1，而其店铺位于城市 5。注意：若道路 (1, 2) 或 (2, 3) 中任意一条被毁，则城市 1 与城市 5 之间将不再存在路径；而若其余任意一条道路被毁，该路径仍可保持连通。因此，对于该商家，答案为 2。