题目描述

小Q来到了一个随机的国度。这个国度由n座城市和m条双向道路构成。因为这个国度崇尚随机，因此m条边是用随机

选择两端点的方式生成的。充满好奇的小Q想在这里进行k次随机的旅行，每次的起点和终点也是随机选择的。在每

次出发之前，他会使用导航系统计算两点间最少需要经过几条道路。请写一个程序，帮助小Q计算两点间的最短路

输入格式

第一行包含3个正整数n,m,k(2<=n<=100000,1<=m<=300000,1<=k<=10000)，分别表示点数、边数和询问数。

接下来m行，每行两个正整数u_i,v_i(1<=u_i,v_i<=n)，表示一条双向道路。输入数据保证不会有重边和自环。

接下来k行，每行两个正整数u_i,v_i(1<=u_i,v_i<=n,u_i!-v_i)，表示一次询问。

输入数据保证随机生成，且除了样例之外均满足n=100000,m=300000。

本题共3组数据。

输出格式

输出k行，每行一个整数，即最少经过的边数，若无解输出-1。

样例

样例输入

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

样例输出

1
2
3
2
-1