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。