Qpwoeirut and Vertices

题意翻译

给出 $n$ 个点， $m$ 条边的不带权连通无向图， $q$ 次询问至少要加完编号前多少的边，才能使得 $[l,r]$ 中的所有点两两连通。 翻译者：蒟蒻君HJT

题目描述

You are given a connected undirected graph with $ n $ vertices and $ m $ edges. Vertices of the graph are numbered by integers from $ 1 $ to $ n $ and edges of the graph are numbered by integers from $ 1 $ to $ m $ . Your task is to answer $ q $ queries, each consisting of two integers $ l $ and $ r $ . The answer to each query is the smallest non-negative integer $ k $ such that the following condition holds: - For all pairs of integers $ (a, b) $ such that $ l\le a\le b\le r $ , vertices $ a $ and $ b $ are reachable from one another using only the first $ k $ edges (that is, edges $ 1, 2, \ldots, k $ ).

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1\le t\le 1000 $ ) — the number of test cases. The first line of each test case contains three integers $ n $ , $ m $ , and $ q $ ( $ 2\le n\le 10^5 $ , $ 1\le m, q\le 2\cdot 10^5 $ ) — the number of vertices, edges, and queries respectively. Each of the next $ m $ lines contains two integers $ u_i $ and $ v_i $ ( $ 1\le u_i, v_i\le n $ ) — ends of the $ i $ -th edge. It is guaranteed that the graph is connected and there are no multiple edges or self-loops. Each of the next $ q $ lines contains two integers $ l $ and $ r $ ( $ 1\le l\le r\le n $ ) — descriptions of the queries. It is guaranteed that that the sum of $ n $ over all test cases does not exceed $ 10^5 $ , the sum of $ m $ over all test cases does not exceed $ 2\cdot 10^5 $ , and the sum of $ q $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, print $ q $ integers — the answers to the queries.

输入输出样例

输入样例 #1

3
2 1 2
1 2
1 1
1 2
5 5 5
1 2
1 3
2 4
3 4
3 5
1 4
3 4
2 2
2 5
3 5
3 2 1
1 3
2 3
1 3

输出样例 #1

0 1 
3 3 0 5 5 
2

说明

Graph from the first test case. The integer near the edge is its number.In the first test case, the graph contains $ 2 $ vertices and a single edge connecting vertices $ 1 $ and $ 2 $ . In the first query, $ l=1 $ and $ r=1 $ . It is possible to reach any vertex from itself, so the answer to this query is $ 0 $ . In the second query, $ l=1 $ and $ r=2 $ . Vertices $ 1 $ and $ 2 $ are reachable from one another using only the first edge, through the path $ 1 \longleftrightarrow 2 $ . It is impossible to reach vertex $ 2 $ from vertex $ 1 $ using only the first $ 0 $ edges. So, the answer to this query is $ 1 $ . Graph from the second test case. The integer near the edge is its number.In the second test case, the graph contains $ 5 $ vertices and $ 5 $ edges. In the first query, $ l=1 $ and $ r=4 $ . It is enough to use the first $ 3 $ edges to satisfy the condition from the statement: - Vertices $ 1 $ and $ 2 $ are reachable from one another through the path $ 1 \longleftrightarrow 2 $ (edge $ 1 $ ). - Vertices $ 1 $ and $ 3 $ are reachable from one another through the path $ 1 \longleftrightarrow 3 $ (edge $ 2 $ ). - Vertices $ 1 $ and $ 4 $ are reachable from one another through the path $ 1 \longleftrightarrow 2 \longleftrightarrow 4 $ (edges $ 1 $ and $ 3 $ ). - Vertices $ 2 $ and $ 3 $ are reachable from one another through the path $ 2 \longleftrightarrow 1 \longleftrightarrow 3 $ (edges $ 1 $ and $ 2 $ ). - Vertices $ 2 $ and $ 4 $ are reachable from one another through the path $ 2 \longleftrightarrow 4 $ (edge $ 3 $ ). - Vertices $ 3 $ and $ 4 $ are reachable from one another through the path $ 3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4 $ (edges $ 2 $ , $ 1 $ , and $ 3 $ ). If we use less than $ 3 $ of the first edges, then the condition won't be satisfied. For example, it is impossible to reach vertex $ 4 $ from vertex $ 1 $ using only the first $ 2 $ edges. So, the answer to this query is $ 3 $ . In the second query, $ l=3 $ and $ r=4 $ . Vertices $ 3 $ and $ 4 $ are reachable from one another through the path $ 3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4 $ (edges $ 2 $ , $ 1 $ , and $ 3 $ ). If we use any fewer of the first edges, nodes $ 3 $ and $ 4 $ will not be reachable from one another.

题目大意：
给定一个由n个顶点和m条边组成的连通无向图，图中顶点编号为1到n，边编号为1到m。需要回答q个查询，每个查询由两个整数l和r组成。每个查询的答案是最小的非负整数k，使得对于所有整数对(a, b)，满足l≤a≤b≤r，顶点a和b可以通过仅使用前k条边（即边1, 2, …, k）相互到达。

输入输出数据格式：
输入格式：
- 第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。
- 每个测试用例的第一行包含三个整数n、m和q（2≤n≤10^5，1≤m, q≤2×10^5），分别表示顶点的数量、边的数量和查询的数量。
- 接下来的m行，每行包含两个整数u_i和v_i（1≤u_i, v_i≤n），表示第i条边的两个端点。
- 确保图是连通的，且没有多条边或自环。
- 接下来的q行，每行包含两个整数l和r（1≤l≤r≤n），描述查询。

输出格式：
- 对于每个测试用例，输出q个整数，表示查询的答案。

输入输出样例：
输入样例 #1：
```
3
2 1 2
1 2
1 1
1 2
5 5 5
1 2
1 3
2 4
3 4
3 5
1 4
3 4
2 2
2 5
3 5
3 2 1
1 3
2 3
1 3
```
输出样例 #1：
```
0 1
3 3 0 5 5
2
```题目大意： 给定一个由n个顶点和m条边组成的连通无向图，图中顶点编号为1到n，边编号为1到m。需要回答q个查询，每个查询由两个整数l和r组成。每个查询的答案是最小的非负整数k，使得对于所有整数对(a, b)，满足l≤a≤b≤r，顶点a和b可以通过仅使用前k条边（即边1, 2, …, k）相互到达。 输入输出数据格式： 输入格式： - 第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。 - 每个测试用例的第一行包含三个整数n、m和q（2≤n≤10^5，1≤m, q≤2×10^5），分别表示顶点的数量、边的数量和查询的数量。 - 接下来的m行，每行包含两个整数u_i和v_i（1≤u_i, v_i≤n），表示第i条边的两个端点。 - 确保图是连通的，且没有多条边或自环。 - 接下来的q行，每行包含两个整数l和r（1≤l≤r≤n），描述查询。 输出格式： - 对于每个测试用例，输出q个整数，表示查询的答案。 输入输出样例： 输入样例 #1： ``` 3 2 1 2 1 2 1 1 1 2 5 5 5 1 2 1 3 2 4 3 4 3 5 1 4 3 4 2 2 2 5 3 5 3 2 1 1 3 2 3 1 3 ``` 输出样例 #1： ``` 0 1 3 3 0 5 5 2 ```