P4320 Road Encounter

# Description In country H, Xiao w decides to travel from city $u$ to city $v$. However, for various reasons, Xiao c is not in city $u$, but Xiao c decides to meet Xiao w somewhere along the way. Because of the road network in country H, the route Xiao w takes from city $u$ to city $v$ is not fixed. To plan time reasonably, Xiao c wants to know how many cities Xiao w will definitely pass through on all possible routes from city $u$ to city $v$. In particular, $u$ and $v$ must also be counted, which means the answer is never less than $2$. For various reasons, Xiao c does not know Xiao w’s exact start and end cities, but Xiao c knows there are only $q$ possible pairs of start and end cities. For each of these $q$ possibilities, Xiao c wants to know the number of cities that Xiao w will definitely pass through. All edges in country H are undirected. Between any two cities, there is at most one direct road. There is no road that connects a city to itself. At all times, the graph is connected.

在 H 国的小 w 决定到从城市 $u$ 到城市 $v$ 旅行，但是此时小 c 由于各种原因不在城市 $u$，但是小 c 决定到在中途与小 w 相遇 由于 H 国道路的原因，小 w 从城市 $u$ 到城市 $v$ 的路线不是固定的，为了合理分配时间，小 c 想知道从城市 $u$ 到城市 $v$ 有多少个城市小 w 一定会经过，特别地，$u, v$ 也必须被算进去，也就是说无论如何答案不会小于 2 由于各种特殊的原因，小 c 并不知道小 w 的起点和终点，但是小 c 知道小 w 的起点和终点只有 $q$ 种可能，所以对于这 $q$ 种可能，小 c 都想知道小 w 一定会经过的城市数 H 国所有的边都是无向边，两个城市之间最多只有一条道路直接相连，没有一条道路连接相同的一个城市 任何时候，H 国不存在城市 $u$ 和城市 $v$ 满足从 $u$ 无法到达 $v$

第一行两个正整数 $n,m$，表示 H 国的城市数，以及道路数。 下面 $m$ 行，每行两个不同的正整数 $u, v$，表示城市 $u$ 到城市 $v$ 之间有一条边。 然后一行一个正整数 $q$。 接下来 $q$ 行，每行两个正整数 $u, v$ 表示小 w 旅行的一种可能的路线

Output $q$ lines, each containing a single positive integer.

From city $1$ to city $5$ there are $4$ possible routes: $1 \to 2 \to 3 \to 4 \to 5$ $1 \to 2 \to 3 \to 5$ $1 \to 3 \to 4 \to 5$ $1 \to 3 \to 5$ It can be seen that Xiao w will always pass through cities $1, 3, 5$, so the answer is $3$. You may assume Xiao w will not visit the same city twice. Of course, even if you think revisiting cities is allowed, it does not affect the answer. Subtask 1: 15 points, $n = 5, q = 50$. Subtask 2: 15 points, $n = 100, q = 5000$. Subtask 3: 20 points, $n = 3000, q = 5 \times 10^5$. Subtask 4: 20 points, $n = 499999, q = 5 \times 10^5, m = n - 1$. Subtask 5: 30 points, $n = q = 5 \times 10^5$. Constraints: For all testdata: $1 \leq n \leq 5 \times 10^5, 1 \leq q \leq 5 \times 10^5, 1 \leq m \leq \min(\frac{n(n-1)}{2}, 10^6)$. Translated by ChatGPT 5