给您一个由 $$$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$$$ 的任何简单路径,所有这些边都将计入查询的答案中。