Description
小Q来到了一个随机的国度。这个国度由n座城市和m条双向道路构成。因为这个国度崇尚随机，因此m条边是用随机
选择两端点的方式生成的。充满好奇的小Q想在这里进行k次随机的旅行，每次的起点和终点也是随机选择的。在每
次出发之前，他会使用导航系统计算两点间最少需要经过几条道路。请写一个程序，帮助小Q计算两点间的最短路
Input
第一行包含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组数据。
Output
输出k行，每行一个整数，即最少经过的边数，若无解输出-1。
由于随机数据，可以直接双向广搜求最短路，特判不连通的情况。
#include<bits/stdc++.h>
const int N=1e5+;
char ib[N*],*ip=ib;
int _(){
int x=;
while(*ip<)++ip;
while(*ip>)x=x*+*ip++-;
return x;
}
int n,m,k,f[N];
std::vector<int>e[N];
int ed[N][],tk=;
int gf(int x){
while(x!=x[f])x=x[f]=x[f][f];
return x;
}
struct{
int q[N],ql,qr;
void clr(){ql=qr=;}
void push(int x,int d){
ed[x][]=tk;
ed[x][]=d;
q[++qr]=x;
}
int pop(){return q[++ql];}
int cnt(){return qr-ql;}
}qa,qb;
int que(){
int a=_(),b=_();
if(a==b)return ;
if(gf(a)!=gf(b))return -;
++tk;
qa.clr(),qb.clr();
qa.push(a,),qb.push(b,-);
for(;;){
for(int t=qa.cnt();t;--t){
int w=qa.pop(),d=ed[w][]+;
for(unsigned i=;i!=e[w].size();++i){
int u=e[w][i];
if(ed[u][]==tk){
if(ed[u][]<)return d-ed[u][]-;
}else qa.push(u,d);
}
}
for(int t=qb.cnt();t;--t){
int w=qb.pop(),d=ed[w][]-;
for(unsigned i=;i!=e[w].size();++i){
int u=e[w][i];
if(ed[u][]==tk){
if(ed[u][]>)return ed[u][]-d-;
}else qb.push(u,d);
}
}
}
}
int main(){
fread(ib,,sizeof(ib),stdin);
n=_(),m=_(),k=_();
for(int i=;i<=n;++i)f[i]=i,e[i].reserve();
for(int i=,a,b;i<m;++i){
a=_(),b=_();
e[a].push_back(b);
e[b].push_back(a);
f[gf(a)]=gf(b);
}
for(int i=;i<=k;++i)printf("%d\n",que());
return ;
}