#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int maxn=1e5+5;
ll fa[maxn][40],depth[maxn];
ll n,m,k;ll pre[maxn];
vector<ll> vec[maxn];
bool vis[maxn];
ll root;
void dfs(ll s,ll step){
depth[s]=step;vis[s]=1;
for(ll i=0;i<vec[s].size();i++){
ll v=vec[s][i];
if(!vis[v]) dfs(v,step+1);
}
}
void bz(){
for(ll j=1;j<=30;j++){
for(ll i=1;i<=n;i++){
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
}
ll LCA(ll u,ll v){
if(depth[u]<depth[v]) swap(u,v);
ll dc=depth[u]-depth[v];
cout<<dc<<endl;
for(ll i=0;i<30;i++){
if((1<<i)&dc){
u=fa[u][i];
}
}
if(u==v) return u;
for(ll i=29;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
}
u=fa[u][0];
return u;
}
int main()
{
cin>>n>>m>>k;
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;
vec[u].push_back(v);
fa[v][0]=u;
pre[v]=1;
}
root=0;
for(ll i=1;i<=n;i++){
if(!pre[i]) root=i;
}
bz();
dfs(root,1);
for(ll i=1;i<=k;i++){
ll u,v;cin>>u>>v;
cout<<LCA(u,v)<<endl;
}
}
/*
4 3 3
4 3
3 1
1 2
*/
Anonytt_
发布了90 篇原创文章 · 获赞 6 · 访问量 4998
私信
关注