CF178B1 Greedy Merchants

在 ABBYY 有一只聪明的“Smart Beaver”。这一次，他开始学习历史。当他读到罗马帝国时，他对商人的生活产生了兴趣。 罗马帝国由 $n$ 个城市组成，编号从 $1$ 到 $n$。还有 $m$ 条双向道路，编号从 $1$ 到 $m$。每条道路连接两个不同的城市。任意两座城市之间最多只有一条道路相连。 我们说城市 $c_1$ 和 $c_2$ 之间存在一条路径，如果存在一个有限的城市序列 $t_1, t_2, ..., t_p$（$p \geq 1$），满足： - $t_1 = c_1$ - $t_p = c_2$ - 对于任意 $i$（$1 \leq i < p$），城市 $t_i$ 和 $t_{i+1}$ 之间有道路相连 已知罗马帝国中的任意两座城市之间都存在路径。 帝国中有 $k$ 个商人，编号从 $1$ 到 $k$。对于每个商人，已知一对数字 $s_i$ 和 $l_i$，其中 $s_i$ 表示该商人的仓库所在城市编号，$l_i$ 表示该商人的商店所在城市编号。仓库和商店可以位于不同的城市，因此商人需要将货物从仓库运送到商店。 我们称一条道路对某个商人来说是“重要的”，如果摧毁这条道路后，该商人无法从仓库到达商店。换句话说，如果没有这条道路，商人的仓库和商店之间不存在路径。罗马帝国的商人非常贪婪，因此每个商人只为对自己重要的道路缴纳税款（每条道路 1 第纳尔）。也就是说，第 $i$ 个商人需要缴纳 $d_i$ 第纳尔的税款，其中 $d_i$（$d_i \geq 0$）是对第 $i$ 个商人来说重要的道路数量。 帝国迎来了征税日。ABBYY 的聪明“Smart Beaver”天性好奇，他决定统计每个商人在这一天缴纳了多少第纳尔。现在他需要你的帮助。

第一行包含两个整数 $n$ 和 $m$，用空格分隔，表示帝国的城市数和道路数。 接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n, a_i \neq b_i$），用空格分隔，表示第 $i$ 条道路连接的两座城市编号。保证任意两座城市之间最多只有一条道路相连，并且罗马帝国中任意两座城市之间都存在路径。 接下来一行包含一个整数 $k$，表示帝国中的商人数。 接下来的 $k$ 行，每行包含两个整数 $s_i$ 和 $l_i$（$1 \leq s_i, l_i \leq n$），用空格分隔，表示第 $i$ 个商人的仓库和商店所在城市编号。 获得 20 分的输入限制： - $1 \leq n \leq 200$ - $1 \leq m \leq 200$ - $1 \leq k \leq 200$ 获得 50 分的输入限制： - $1 \leq n \leq 2000$ - $1 \leq m \leq 2000$ - $1 \leq k \leq 2000$ 获得 100 分的输入限制： - $1 \leq n \leq 10^5$ - $1 \leq m \leq 10^5$ - $1 \leq k \leq 10^5$

输出恰好 $k$ 行，第 $i$ 行输出一个整数 $d_i$，表示第 $i$ 个商人需要缴纳的第纳尔数量。

下图展示了给定样例的示意图。  我们来描述第一个商人的结果。该商人的仓库位于城市 $1$，商店位于城市 $5$。可以注意到，如果道路 $(1,2)$ 或 $(2,3)$ 被摧毁，城市 $1$ 和 $5$ 之间将不再有路径。如果摧毁其他任何道路，路径仍然存在。因此对于该商人，答案是 $2$。 由 ChatGPT 4.1 翻译