A8513 | Greedy Merchants

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.

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