A104751.雾港实验室的神秘联通块

雾港实验室正在搭建一张由 $n$ 个终端组成的通信网络（编号为 $1\sim n$）。网络一开始没有任何连线。接下来实验室会按时间顺序进行 $m$ 次接线操作：在第 $t$ 次操作时，会新增一条无向连线 $(a_t,b_t)$，从这时起这条连线会一直存在。

有些研究小组会在之后来问网络的连通情况。给出一对终端 $(u,v)$，他们关心的是：最早在第几次接线操作之后，终端 $u$ 与终端 $v$ 已经可以通过若干条连线互相到达（也就是在只考虑前 $t$ 条新增连线时，$u$ 与 $v$ 处在同一个连通块中）。

我们把“第 $0$ 次接线”定义为尚未进行任何操作的初始状态（此时没有边）。显然如果 $u=v$，那么答案为 $0$。

请你对每个询问输出最早连通时刻；若直到第 $m$ 次接线后仍不连通，则输出 $-1$。

第一行三个整数 $n,m,q$。

接下来 $m$ 行，第 $t$ 行两个整数 $a_t,b_t$，表示第 $t$ 次操作新增连线 $(a_t,b_t)$。

接下来 $q$ 行，每行两个整数 $u,v$，表示一个询问。

输出 $q$ 行，每行一个整数，表示对应询问的答案（最早连通的操作编号），或 $-1$。

样例解释

• 前 $2$ 条边加入后，$1$ 与 $3$ 已经连通，所以 $(1,3)$ 的答案为 $2$；
• 直到第 $4$ 条边加入后，$3$ 与 $4$ 才连上，从而把 $\{1,2,3\}$ 与 $\{4,5\}$ 连成一块，因此 $(1,5)$ 与 $(2,5)$ 的答案都是 $4$；
• $(4,4)$ 永远成立，答案为 $0$。

数据范围

• $1\le n\le 200000$
• $1\le m\le 200000$
• $1\le q\le 200000$
• $1\le a_t,b_t,u,v\le n$

测试点编号	$n,m,q$ 上界
$1\sim4$	$n,m,q\le 20$
$5\sim10$	$n,m,q\le 10000$
$11\sim20$	$n,m,q\le 200000$

---