← 返回题目列表

Codeforces · 1706/E

E. Qpwoeirut 和顶点

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

给你一个连通的无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。图的顶点由从 $$$1$$$ 到 $$$n$$$ 的整数编号,图的边由 $$$1$$$ 到 $$$m$$$ 的整数编号。

你的任务是回答 $$$q$$$ 查询,每个查询由两个整数 $$$l$$$ 和 $$$r$$$ 组成。每个查询的答案是满足以下条件的最小非负整数 $$$k$$$:

- 对于所有整数对 $$$(a, b)$$$ 使得 $$$l\le a\le b\le r$$$,顶点 $$$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$$$。

输出

对于每个测试用例,打印 $$$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 \longleftrightarrow 2$$$ 相互到达顶点 $$$1$$$ 和 $$$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$$$ 相互访问)。

如果我们使用的第一条边少于$$$3$$$,则条件将不被满足。例如,仅使用前 $$$2$$$ 边不可能从顶点 $$$1$$$ 到达顶点 $$$4$$$。因此,该查询的答案是 $$$3$$$。

在第二个查询中,$$$l=3$$$ 和 $$$r=4$$$。顶点 $$$3$$$ 和 $$$4$$$ 可通过路径 $$$3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$$$(边 $$$2$$$、$$$1$$$ 和 $$$3$$$ 相互到达。如果我们使用更少的第一条边,则节点 $$$3$$$ 和 $$$4$$$ 将无法相互访问。