#T2254. 新建道路查询(New Roads Queries)

新建道路查询(New Roads Queries)

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

板块: Advanced Techniques

时限: 1.00 s | 内存: 512 MB

题目描述

Byteland 有 nn 座城市,但彼此之间没有道路。不过,每天都会修建一条新道路,总共会修建 mm 条道路。

你的任务是处理 qq 个查询,形式为:「经过多少天后,我们才能第一次从城市 aa 到达城市 bb?」

输入

第一行有三个整数 nn、mm 和 qq:城市数量、道路数量与查询数量。城市编号为 1,2,…,n1,2,\dots,n。

之后有 mm 行按修建顺序描述道路。每行有两个整数 aa 和 bb:城市 aa 与城市 bb 之间将有一条道路。

最后有 qq 行描述查询。每行有两个整数 aa 和 bb:我们希望从城市 aa 到达城市 bb。

输出

对每个查询,输出所需天数;如果永远无法到达,则输出 −1-1。

数据范围

1≤n,m,q≤2⋅1051 \le n, m, q \le 2 \cdot 10^5 1≤a,b≤n1 \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