题目描述

Byteland 有 $n$ 座城市，起初没有道路。之后每天会修建一条新道路，一共会修建 $m$ 条道路。

你需要处理 $q$ 次询问：城市 $a$ 和城市 $b$ 最早在第几天可以互相到达？

输入格式

第一行包含三个整数 $n,m,q$，分别表示城市数量、道路数量和询问数量。城市编号为 $1,2,\ldots,n$。

接下来 $m$ 行按修建顺序描述道路。每行包含两个整数 $a,b$，表示当天会修建城市 $a$ 与 $b$ 之间的道路。

最后 $q$ 行，每行包含两个整数 $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