Greedy Merchants

题意翻译

##### 题目描述 在 ABBYY 生活着一只聪明的海狸。他现在在学习历史。当他从书上读到罗马帝国的时候，他对商人们的生活产生了兴趣。 罗马帝国由编号为 1 到 n 的 n 座城市构成。同时还有编号为 1 到 m 的 m 条双向路连接着这些城市。每一条路都连接着不同的城市。保证任意两个城市间最多只有一条路。 我们将一个城市序列t1, t2, t3, ....tp（p >= 1）称为城市 c1 和 c2 间的一条**路径**，当： ·t1 = c1 ·tp = c2 ·对于任意一个 i （1 <= i < p），城市 ti 与 ti + 1 间有一条道路链接。 保证罗马帝国的任意两个城市间都存在着**路径**。 在帝国里有标号为 1 到 k 的 k 个商人。对于每一个商人，我们有 si 和 li 一对数。 si 是 i 号商人的家所在的城市的编号，而 li 是他的商所在的城市的编号。他的商店和家可能在不同的城市，所以商人们可能需要把商品从家里搬到商店。 我们将一条路称为**重要的** ，当且仅当这条路被摧毁时，商人将无法从家到达他的商店。罗马的商人们非常的贪婪，所以每一个商人仅会在对他来说是**重要的**路上交税（一第纳尔）。换句话说，每一个商人需要交 di 的税， di （di >= 0）是对于第 i 个商人来说**重要的**路的数量。 收税的日子到了。来自 ABBYY 的聪明的海狸非常的好奇，所以他决定统计每一个商人需要交多少第纳尔的税。现在他需要你的帮助。 ##### 输入格式 输入的第一行包含两个整数 n 和 m。 n 表示城市的数量， m 表示路的数量。 下面的 m 行每行包含两个整数 ai 和 bi， 表示第 i 条路连接的两个城市。保证两个城市间最多只有一条路并且任意两个城市间都存在一条**路径**。 下一行包含单独一个整数 k，表示商人的数量。 下面的 k 行每行包含 si， li 两个整数，分别表示第 i 个商人的家和商店所在城市的编号。 ##### 数据范围 对于 20% 的数据： ·1 <= n <= 200 ·1 <= m <= 200 ·1 <= k <= 200 ------------ 对于 50% 的数据： ·1 <= n <= 2000 ·1 <= m <= 2000 ·1 <= k <= 2000 ------------ 对于 100% 的数据： ·1 <= n <= 1e5 ·1 <= m <= 1e5 ·1 <= k <= 1e5 ##### 输出格式 输出 k 行数，每行单独一个整数表示第 i 个商人要交多少第纳尔的税。 ##### 输入输出样例 略 ##### 样例解释 图略（看下面） 第一个商人的家在 1 号城市，商店在 5 号城市。如果（1，2）或者（2，3）这两条路被摧毁其中一条，在城市 1 和 5 间就不存在路径了。如果任何其他路被摧毁，都不会对路径产生影响。所以 1 号商人需要交 2 第纳尔的税。

题目描述

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.

输入输出格式

输入格式

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<=10^{5} $ - $ 1<=m<=10^{5} $ - $ 1<=k<=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.

输入输出样例

输入样例 #1

7 8
1 2
2 3
3 4
4 5
5 6
5 7
3 5
4 7
4
1 5
2 4
2 6
4 7

输出样例 #1

2
1
2
0

说明

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 $ .