← 返回题目列表

Codeforces · 178/B1

B1. 贪婪的商人

中文机器翻译题面 查看原题

ABBYY 生活着一只美妙的智能海狸。这一次,他开始学习历史。当他了解罗马帝国时,他对商人的生活产生了兴趣。

罗马帝国由 n 个城市组成,编号从 1 到 n。它还具有 m 条双向道路,编号从 1 到 m。每条道路连接两个不同的城市。任何两个城市仅由一条道路连接。

如果存在城市 t1, t2, ..., tp (p ≥ 1) 的有限序列,则我们说城市 c1 和 c2 之间存在一条路径,使得:

- t1 = c1
- tp = c2
- 对于任意 i (1 ≤ i < p),城市 ti 和 ti + 1 通过道路连接

我们知道罗马帝国的任何两个城市之间都存在一条路径。

在帝国中,住着 k 位商人,编号从 1 到 k。对于每个商人,我们知道一对数字si和li,其中si是该商人的仓库所在城市的编号,li是他的商店所在城市的编号。商店和仓库可能位于不同的城市,因此商家必须将货物从仓库运送到商店。

如果这条路的破坏威胁到商人的灭亡,我们就称这条路对商人来说很重要,也就是说,没有这条路,就没有从商人的仓库到他的商店的路径。罗马帝国的商人非常贪婪,因此每个商人只为那些对他来说重要的道路缴纳税款(1第纳尔)。换句话说,每个商人缴纳 di 第纳尔的税,其中 di (di ≥ 0) 是对第 i 个商人重要的道路数量。

帝国的征税日到来了。 ABBYY 的聪明海狸生性好奇,所以他决定数一数当天每个商人支付了多少第纳尔。现在他需要你的帮助。

输入

第一输入行包含两个整数n和m,用空格分隔,n是城市数量,m是帝国道路数量。

接下来的 m 行包含整数对 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi),用空格分隔 — 第 i 条路连接的城市数量。保证任意两个城市之间不超过一条道路相连,并且罗马帝国的任意两个城市之间都存在一条路径。

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

接下来的k行是一对整数si,li(1≤si,li≤n),中间用空格隔开,——si是第i个商户的仓库所在城市的编号,li是第i个商户的店铺所在的城市的编号。

获得 20 点的输入限制为:

- 1 ≤ n ≤ 200
- 1 ≤ 米 ≤ 200
- 1 ≤ k ≤ 200

获得 50 点的输入限制为:

- 1 ≤ n ≤ 2000
- 1 ≤ 米 ≤ 2000
- 1 ≤ k ≤ 2000

获得 100 点的输入限制为:

- 1 ≤ n ≤ 105
- 1 ≤ 米 ≤ 105
- 1 ≤ k ≤ 105

输出

精确打印 k 行,第 i 行应包含一个整数 di — 第 i 个商家支付的第纳尔数。

示例

输入 #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

注意

给定的示例如下图所示。

让我们描述一下第一个商家的结果。商人的仓库位于城市 1,他的商店位于城市 5。请注意,如果道路 (1, 2) 或 (2, 3) 被破坏,则城市 1 和城市 5 之间将不再有任何路径。如果任何其他道路被破坏,该道路将被保留。这就是为什么对于给定的商家来说答案是 2。