A6894. Qpwoeirut and Vertices
编程题
提高+/省选-
知识点
题目描述
给定一个连通的无向图，包含 $n$ 个顶点和 $m$ 条边。顶点编号为 $1$ 到 $n$，边编号为 $1$ 到 $m$。
你的任务是回答 $q$ 个询问，每个询问包含两个整数 $l$ 和 $r$。对于每个询问，输出最小的非负整数 $k$，使得满足以下条件：
- 对于所有满足 $l\le a\le b\le r$ 的整数对 $(a, b)$，顶点 $a$ 和 $b$ 仅使用前 $k$ 条边（即第 $1,2,\ldots,k$ 条边）即可互相到达。
你的任务是回答 $q$ 个询问，每个询问包含两个整数 $l$ 和 $r$。对于每个询问，输出最小的非负整数 $k$，使得满足以下条件：
- 对于所有满足 $l\le a\le b\le r$ 的整数对 $(a, b)$，顶点 $a$ 和 $b$ 仅使用前 $k$ 条边（即第 $1,2,\ldots,k$ 条边）即可互相到达。
输入格式
第一行包含一个整数 $t$（$1\le t\le 1000$），表示测试用例的数量。
每个测试用例的第一行包含三个整数 $n$、$m$ 和 $q$（$2\le n\le 10^5$，$1\le m, q\le 2\cdot 10^5$），分别表示顶点数、边数和询问数。
接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i, v_i\le n$），表示第 $i$ 条边的两个端点。
保证图是连通的，且没有重边和自环。
接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1\le l\le r\le n$），表示一次询问。
保证所有测试用例中 $n$ 的总和不超过 $10^5$，$m$ 的总和不超过 $2\cdot 10^5$，$q$ 的总和不超过 $2\cdot 10^5$。
每个测试用例的第一行包含三个整数 $n$、$m$ 和 $q$（$2\le n\le 10^5$，$1\le m, q\le 2\cdot 10^5$），分别表示顶点数、边数和询问数。
接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i, v_i\le n$），表示第 $i$ 条边的两个端点。
保证图是连通的，且没有重边和自环。
接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1\le l\le r\le n$），表示一次询问。
保证所有测试用例中 $n$ 的总和不超过 $10^5$，$m$ 的总和不超过 $2\cdot 10^5$，$q$ 的总和不超过 $2\cdot 10^5$。
输出格式
对于每个测试用例，输出 $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
说明/提示
第一组测试数据的图。每条边旁的数字是其编号。在第一组测试数据中，图包含 $2$ 个顶点和一条连接顶点 $1$ 和 $2$ 的边。
第一个询问中，$l=1$，$r=1$。任何顶点都能到达自身，因此答案为 $0$。
第二个询问中，$l=1$，$r=2$。顶点 $1$ 和 $2$ 仅使用第一条边即可互相到达，路径为 $1 \longleftrightarrow 2$。如果只使用前 $0$ 条边，则无法从 $1$ 到达 $2$，所以答案为 $1$。
 第二组测试数据的图。每条边旁的数字是其编号。在第二组测试数据中，图包含 $5$ 个顶点和 $5$ 条边。
第一个询问中，$l=1$，$r=4$。只需使用前 $3$ 条边即可满足题目条件：
- 顶点 $1$ 和 $2$ 通过路径 $1 \longleftrightarrow 2$（边 $1$）互相到达。
- 顶点 $1$ 和 $3$ 通过路径 $1 \longleftrightarrow 3$（边 $2$）互相到达。
- 顶点 $1$ 和 $4$ 通过路径 $1 \longleftrightarrow 2 \longleftrightarrow 4$（边 $1$ 和 $3$）互相到达。
- 顶点 $2$ 和 $3$ 通过路径 $2 \longleftrightarrow 1 \longleftrightarrow 3$（边 $1$ 和 $2$）互相到达。
- 顶点 $2$ 和 $4$ 通过路径 $2 \longleftrightarrow 4$（边 $3$）互相到达。
- 顶点 $3$ 和 $4$ 通过路径 $3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$（边 $2$、$1$ 和 $3$）互相到达。
如果只使用前 $2$ 条边，则无法满足条件。例如，只用前 $2$ 条边无法从 $1$ 到达 $4$，所以答案为 $3$。
第二个询问中，$l=3$，$r=4$。顶点 $3$ 和 $4$ 通过路径 $3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$（边 $2$、$1$ 和 $3$）互相到达。如果再少用一条边，则 $3$ 和 $4$ 无法互达。
第一个询问中，$l=1$，$r=1$。任何顶点都能到达自身，因此答案为 $0$。
第二个询问中，$l=1$，$r=2$。顶点 $1$ 和 $2$ 仅使用第一条边即可互相到达，路径为 $1 \longleftrightarrow 2$。如果只使用前 $0$ 条边，则无法从 $1$ 到达 $2$，所以答案为 $1$。
 第二组测试数据的图。每条边旁的数字是其编号。在第二组测试数据中，图包含 $5$ 个顶点和 $5$ 条边。
第一个询问中，$l=1$，$r=4$。只需使用前 $3$ 条边即可满足题目条件：
- 顶点 $1$ 和 $2$ 通过路径 $1 \longleftrightarrow 2$（边 $1$）互相到达。
- 顶点 $1$ 和 $3$ 通过路径 $1 \longleftrightarrow 3$（边 $2$）互相到达。
- 顶点 $1$ 和 $4$ 通过路径 $1 \longleftrightarrow 2 \longleftrightarrow 4$（边 $1$ 和 $3$）互相到达。
- 顶点 $2$ 和 $3$ 通过路径 $2 \longleftrightarrow 1 \longleftrightarrow 3$（边 $1$ 和 $2$）互相到达。
- 顶点 $2$ 和 $4$ 通过路径 $2 \longleftrightarrow 4$（边 $3$）互相到达。
- 顶点 $3$ 和 $4$ 通过路径 $3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$（边 $2$、$1$ 和 $3$）互相到达。
如果只使用前 $2$ 条边，则无法满足条件。例如，只用前 $2$ 条边无法从 $1$ 到达 $4$，所以答案为 $3$。
第二个询问中，$l=3$，$r=4$。顶点 $3$ 和 $4$ 通过路径 $3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$（边 $2$、$1$ 和 $3$）互相到达。如果再少用一条边，则 $3$ 和 $4$ 无法互达。