给你一个连通的无向图,其中有 $$$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$$$ 将无法相互访问。