Migrated from Lutece 3188 时间穿梭

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

「给我听好了，你们这些蠢货们！」

「你们这些家伙想要得到的 XX，已经不在这里了！」

「在这个时代，已经不存在了！」

「真可惜呐，给我好好的后悔吧！然后感到恐惧吧！」

「我凤凰院凶真，对你们这些家伙也好，对命运也是，都不会输！」

「我，一定会，把命运石之门找出来！」

「这就是！本大爷的！选择！」

---

$$$$

胸针能够乘坐时间机器来实现时间穿梭。具体来说，有 $n$ 个时间点，时间点可以被编号为 $1 \sim n$。有 $m$ 个时间隧道，连接了其中两个不同的时间点，代表能从其中任意一个时间点到达另一个时间点（即双向），且也被编号为 $1 \sim m$。保证从任意时间点出发，都能通过某些时间隧道到达另一个时间点。

胸针会进去 $q$ 次时间旅行，每次给出一个数对 $l, r$，代表胸针想要在编号为 $l \sim r$ 之间的时间点内畅通无阻，即对于 $\forall u\in[l,r],\forall v\in[l,r]$，胸针都能从 $u$ 出发到达 $v$。

为此，胸针每次时间旅行都会选择一些时间隧道，一次时间旅行的代价为：所选择的时间隧道中的编号最大值。他想要每次时间旅行的代价最小。

胸针忙着时间旅行，于是将这个问题抛给了你。

Input

第一行，第一个正整数 $t$，代表测试组数。

对于每一个测试组：

第一行有三个正整数，$n, m, q$，分别代表时间点的数量，时间隧道的数量，以及时间旅行的次数。

接下来 $m$ 行，每行两个整数 $u_i$, $v_i$，代表一个时间隧道连接的连个时间点编号。

接下来 $q$ 行，每行两个整数 $l, r$，代表每次时间旅行的区间。

Output

对于每个测试组，输出一行，有 $q$ 个以空格分开的整数，代表每次时间旅行的最小代价。

Samples

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

0 1
3 3 0 5 5
2

Constraints

$1 \le t \le 1000$

$2 \le n \le 10^5$

$1 \le m, q \le 2 \times 10^5$

$1 \le u_i, v_i \le n$

$1 \le l \le r \le n$

保证所有测试组的 $n$ 之和不超过 $10^5$，$m$ 之和不超过 $2 \times 10^5$，$q$ 之和不超过 $2 \times 10^5$

Note

神中神：

星の奏でる歌

GATE OF STEINER

Karma

Resources

2024 UESTC ICPC Training for Graph