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}$
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$ .
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$ .
输入输出样例
输入 #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$ .
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$ .