309947: CF1763F. Edge Queries
Memory Limit：256 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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.输入输出格式
输入格式
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 $ ).
输出格式
For each query, output a single integer — answer to the query.
输入输出样例
输入样例 #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说明
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.Input
题意翻译
给定一张 $n$ 个点，$m$ 条边的无向连通图，它满足：对于任意点，包含它的任何简单环长度相等。 你需要回答 $q$ 次询问，每次询问两个点 $a,b$，求出被至少一条 $a\to b$ 的简单路径包含的边中，有多少条满足断掉它后 $a,b$ 仍然连通。 $1\le n,m,q\le 2\times 10^5$。Output
**题目描述**
给定一个无向、连通的图，包含 $ 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 \times 10^5 $，$ 1 \le m \le \min(2 \times 10^5, \frac{n \times (n-1)}{2}) $）——图中节点和边的总数。
接下来的 $ m $ 行每行包含两个整数 $ u $ 和 $ v $ （$ 1 \le u, v \le n $，$ u \neq v $）——描述一条边，意味着节点 $ u $ 和 $ v $ 相连。
保证图中任意一对顶点之间最多只有一条边，并且给定的图是连通的。
下一行包含一个整数 $ q $ （$ 1 \le q \le 2 \times 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 $ 的简单路径，所有这些边都将被计入查询的答案中。**题目描述** 给定一个无向、连通的图，包含 $ 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 \times 10^5 $，$ 1 \le m \le \min(2 \times 10^5, \frac{n \times (n-1)}{2}) $）——图中节点和边的总数。 接下来的 $ m $ 行每行包含两个整数 $ u $ 和 $ v $ （$ 1 \le u, v \le n $，$ u \neq v $）——描述一条边，意味着节点 $ u $ 和 $ v $ 相连。 保证图中任意一对顶点之间最多只有一条边，并且给定的图是连通的。 下一行包含一个整数 $ q $ （$ 1 \le q \le 2 \times 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 $ 的简单路径，所有这些边都将被计入查询的答案中。
给定一个无向、连通的图，包含 $ 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 \times 10^5 $，$ 1 \le m \le \min(2 \times 10^5, \frac{n \times (n-1)}{2}) $）——图中节点和边的总数。
接下来的 $ m $ 行每行包含两个整数 $ u $ 和 $ v $ （$ 1 \le u, v \le n $，$ u \neq v $）——描述一条边，意味着节点 $ u $ 和 $ v $ 相连。
保证图中任意一对顶点之间最多只有一条边，并且给定的图是连通的。
下一行包含一个整数 $ q $ （$ 1 \le q \le 2 \times 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 $ 的简单路径，所有这些边都将被计入查询的答案中。**题目描述** 给定一个无向、连通的图，包含 $ 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 \times 10^5 $，$ 1 \le m \le \min(2 \times 10^5, \frac{n \times (n-1)}{2}) $）——图中节点和边的总数。 接下来的 $ m $ 行每行包含两个整数 $ u $ 和 $ v $ （$ 1 \le u, v \le n $，$ u \neq v $）——描述一条边，意味着节点 $ u $ 和 $ v $ 相连。 保证图中任意一对顶点之间最多只有一条边，并且给定的图是连通的。 下一行包含一个整数 $ q $ （$ 1 \le q \le 2 \times 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 $ 的简单路径，所有这些边都将被计入查询的答案中。