A7223 | $雾港实验室的神秘联通块$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港实验室正在搭建一张由 $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$。

输入 #1

输出 #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$ ---

C++ 编辑器

输入

输出