6966. 新建道路查询 (New Roads Queries)
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 拜特兰（Byteland）共有 $n$ 个城市，起初它们之间没有任何道路连接。此后，每天都会新建一条道路，一共将新建 $m$ 条道路。 你的任务是处理 $q$ 个查询，每个查询的形式为：“在经过多少天后，我们能够首次从城市 $a$ 旅行到城市 $b$？” ## 输入格式 第一行包含三个整数 $n, m$ 和 $q$，分别表示城市数、道路数以及查询次数。城市编号为 $1, 2, \dots, n$。 接下来 $m$ 行描述按修建顺序排列的道路。每行包含两个整数 $a$ 和 $b$，表示在第 $i$ 天会在城市 $a$ 和城市 $b$ 之间新建一条无向道路。 最后 $q$ 行描述查询。每行包含两个整数 $a$ 和 $b$，代表你想询问从 $a$ 首次可达 $b$ 的天数。 ## 输出格式 对于每个查询，输出一个整数表示所需的天数；如果两者永远无法连通，则输出 `-1`。 ## 输入输出样例 ### 输入 #1 ``` 5 4 3 1 2 2 3 1 3 2 5 1 3 3 4 3 5 ``` ### 输出 #1 ``` 2 -1 4 ``` ## 说明/提示 ### 数据规模与约定 * $1 \le n, m, q \le 2 \cdot 10^5$ * $1 \le a, b \le n$