CF1763F.Edge Queries

You are given an undirected, connected graph of $n$ nodes and $m$ edges. All nodes $u$ of the graph satisfy the following:

• Let $S_u$ be the set of vertices in the longest simple cycle starting and ending at $u$.
• Let $C_u$ be the union of the sets of vertices in any simple cycle starting and ending at $u$.
• $S_u = C_u$.

You need to answer $q$ queries.

For each query, you will be given node $a$ and node $b$. Out of all the edges that belong to any simple path from $a$ to $b$, count the number of edges such that if you remove that edge, $a$ and $b$ are reachable from each other.

给你一个包含 $n$ 个节点和 $m$ 条边的无向连通图。图中所有节点 $u$ 均满足以下条件：

• 设 $S_u$ 为从 $u$ 出发并回到 $u$ 的最长简单环所包含的顶点集合；
• 设 $C_u$ 为所有从 $u$ 出发并回到 $u$ 的简单环的顶点集合的并集；
• $S_u = C_u$。

你需要回答 $q$ 个查询。

对于每个查询，给定节点 $a$ 和节点 $b$。在所有属于 $a$ 到 $b$ 的任意简单路径的边中，统计满足如下条件的边的数量：若删除该边，$a$ 和 $b$ 仍彼此可达。

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le \min$($2 \cdot 10^5$, $(n \cdot (n-1))/2$)) — the total number of nodes and edges in the graph, respectively.

The next $m$ lines contain two integers $u$ and $v$ ($1 \le$ $u$, $v$ $\le n$, $u \neq v$) — describing an edge, implying that nodes $u$ and $v$ are connected to each other.

It is guaranteed that there is at most one edge between any pair of vertices in the graph and the given graph is connected.

The next line contains a single integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

Then $q$ lines follow, each representing a query. Each query contains two integers $a$ and $b$ ($1 \le$ $a$, $b$ $\le n$).

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le \min(2 \cdot 10^5,\ (n \cdot (n-1))/2)$），分别表示图中节点和边的总数。

接下来的 $m$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u,\ v \le n$，$u \neq v$），描述一条边，表示节点 $u$ 与 $v$ 相互连通。

保证图中任意一对顶点之间至多存在一条边，且给定的图是连通的。

下一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示查询的数量。

随后是 $q$ 行，每行代表一个查询。每个查询包含两个整数 $a$ 和 $b$（$1 \le a,\ b \le n$）。

For each query, output a single integer — answer to the query.

对于每个查询，输出一个整数——该查询的答案。

The graph in the first sample is :

The first query is $(1, 4)$. There are $5$ total edges that belong to any simple path from $1$ to $4$. Edges $(3, 4), (4, 5), (5, 3)$ will be counted in the answer to the query.

The fourth query is $(2, 8)$. There is only one simple path from $2$ to $8$, thus none of the edges will be counted in the answer to the query.

The fifth query is $(7, 10)$. There are $4$ total edges that belong to any simple path from $7$ to $10$, all of them will be counted in the answer to the query.

第一个样例中的图如下所示：

第一个查询为 $(1, 4)$。在任意一条从 $1$ 到 $4$ 的简单路径中，共有 $5$ 条边；其中边 $(3, 4)$、$(4, 5)$、$(5, 3)$ 将被计入该查询的答案。

第四个查询为 $(2, 8)$。从 $2$ 到 $8$ 仅存在唯一一条简单路径，因此该查询的答案中不计入任何边。

第五个查询为 $(7, 10)$。在任意一条从 $7$ 到 $10$ 的简单路径中，共有 $4$ 条边；这 $4$ 条边均将被计入该查询的答案。