链接: https://cses.fi/problemset/task/2101

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

Byteland 有 $n$ 座城市，但彼此之间没有道路。不过，每天都会修建一条新道路，总共会修建 $m$ 条道路。

你的任务是处理 $q$ 个查询，形式为：「经过多少天后，我们才能第一次从城市 $a$ 到达城市 $b$？」

输入

第一行有三个整数 $n$、$m$ 和 $q$：城市数量、道路数量与查询数量。城市编号为 $1,2,\dots,n$。

之后有 $m$ 行按修建顺序描述道路。每行有两个整数 $a$ 和 $b$：城市 $a$ 与城市 $b$ 之间将有一条道路。

最后有 $q$ 行描述查询。每行有两个整数 $a$ 和 $b$：我们希望从城市 $a$ 到达城市 $b$。

输出

对每个查询，输出所需天数；如果永远无法到达，则输出 $-1$。

数据范围

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

样例输入

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

样例输出

2
-1
4