CF178B3.Greedy Merchants

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 nn cities numbered from 11 to nn . It also had mm bidirectional roads numbered from 11 to mm . 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 c1c_{1} and c2c_{2} if there exists a finite sequence of cities t1,t2,...,tpt_{1},t_{2},...,t_{p} (p>=1)(p>=1) such that:

  • t1=c1t_{1}=c_{1}
  • tp=c2t_{p}=c_{2}
  • for any ii (1<=i<p)(1<=i<p) , cities tit_{i} and ti+1t_{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 kk merchants lived numbered from 11 to kk . For each merchant we know a pair of numbers sis_{i} and lil_{i} , where sis_{i} is the number of the city where this merchant's warehouse is, and lil_{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 did_{i} dinars of tax, where did_{i} ( di>=0d_{i}>=0 ) is the number of roads important for the ii -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 nn and mm , separated by a space, nn is the number of cities, and mm is the number of roads in the empire.

The following mm lines contain pairs of integers aia_{i} , bib_{i} (1<=ai,bi<=n,aibi)(1<=a_{i},b_{i}<=n,a_{i}≠b_{i}) , separated by a space — the numbers of cities connected by the ii -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 kk — the number of merchants in the empire.

The following kk lines contain pairs of integers sis_{i} , lil_{i} (1<=si,li<=n)(1<=s_{i},l_{i}<=n) , separated by a space, — sis_{i} is the number of the city in which the warehouse of the ii -th merchant is located, and lil_{i} is the number of the city in which the shop of the ii -th merchant is located.

The input limitations for getting 20 points are:

  • 1<=n<=2001<=n<=200
  • 1<=m<=2001<=m<=200
  • 1<=k<=2001<=k<=200

The input limitations for getting 50 points are:

  • 1<=n<=20001<=n<=2000
  • 1<=m<=20001<=m<=2000
  • 1<=k<=20001<=k<=2000

The input limitations for getting 100 points are:

  • 1<=n<=1051<=n<=10^{5}
  • 1<=m<=1051<=m<=10^{5}
  • 1<=k<=1051<=k<=10^{5}

输出格式

Print exactly kk lines, the ii -th line should contain a single integer did_{i} — the number of dinars that the ii -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 11 and his shop is in city 55 . Let us note that if either road, (1,2)(1,2) or (2,3)(2,3) is destroyed, there won't be any path between cities 11 and 55 anymore. If any other road is destroyed, the path will be preserved. That's why for the given merchant the answer is 22 .

首页