New Roads Queries

题目描述

在 Byteland 有 $n$ 个城市，但城市之间没有道路。然而，每一天会新建一条道路。总共会建成 $m$ 条道路。 你的任务是处理 $q$ 个查询，查询形式为：“在第多少天之后我们可以第一次从城市 a 旅行到城市 b？”。

输入格式

第一行包含三个整数 $n, m$ 和 $q$：城市数、道路数和查询数。城市编号为 $1,2,\dots,n$。 接下来有 $m$ 行描述按建造顺序的道路。每行有两个整数 $a$ 和 $b$：表示将会在城市 $a$ 和 $b$ 之间建一条道路。 最后有 $q$ 行描述查询。每行有两个整数 $a$ 和 $b$：我们希望从城市 $a$ 旅行到城市 $b$。

输出格式

对于每个查询，输出天数，如果永远不可能则输出 $-1$。

5 4 3
1 2
2 3
1 3
2 5
1 3
3 4
3 5

2
-1
4

提示

$1 \le n, m, q \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES2101|先进技术

来源

CSES2101|先进技术