← 返回题目列表

Codeforces · 1763/F

F. 边缘查询

中文机器翻译题面 查看原题

给您一个由 $$$n$$$ 节点和 $$$m$$$ 边组成的无向连通图。图的所有节点 $$$u$$$ 满足以下条件:

- 设 $$$S_u$$$ 为最长简单循环中以 $$$u$$$ 开始和结束的顶点集。
- 设 $$$C_u$$$ 为以 $$$u$$$ 开始和结束的任何简单循环中顶点集的并集。
- $$$S_u = C_u$$$。

您需要回答 $$$q$$$ 查询。

对于每个查询,您将获得节点 $$$a$$$ 和节点 $$$b$$$。在属于从 $$$a$$$ 到 $$$b$$$ 的任何简单路径的所有边中,计算边的数量,以便如果删除该边,$$$a$$$ 和 $$$b$$$ 可以相互到达。

输入

第一行包含两个整数 $$$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$$$)。

输出

对于每个查询,输出一个整数 - 查询的答案。

示例

输入 #1

10 11
1 2
2 3
3 4
4 5
5 3
2 7
7 9
9 10
10 6
6 7
1 8
5
1 4
5 10
3 5
2 8
7 10

输出 #1

3
7
3
0
4

输入 #2

13 15
1 2
2 3
3 4
4 1
2 4
3 5
5 6
6 7
6 8
7 9
9 10
8 7
10 11
10 12
10 13
6
9 11
1 5
1 8
5 2
5 12
12 13

输出 #2

0
5
8
5
3
0

注意

第一个示例中的图表是:

第一个查询是 $$$(1, 4)$$$。共有 $$$5$$$ 条边属于从 $$$1$$$ 到 $$$4$$$ 的任何简单路径。边 $$$(3, 4), (4, 5), (5, 3)$$$ 将计入查询的答案中。

第四个查询是 $$$(2, 8)$$$。从 $$$2$$$ 到 $$$8$$$ 只有一条简单路径,因此查询的答案中不会计算任何边。

第五个查询是 $$$(7, 10)$$$。共有 $$$4$$$ 条边属于从 $$$7$$$ 到 $$$10$$$ 的任何简单路径,所有这些边都将计入查询的答案中。