```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,s,f[N][19],g[N][19],dep[N];
vector<int>G[N];
void Add(int,int);
void dfs(int u,int fa){
for(int v:G[u])
if(v!=fa) f[v][0]=u,dep[v]=dep[u]+1,dfs(v,u);
}
void init(){
for(int j=1;(1<<j)<=n;++j)
for(int i=1;i<=n;++i)
f[i][j]=f[f[i][j-1]][j-1];
}
int LCA(int u,int v){
if(dep[v]>dep[u]) swap(u,v);
for(int x=dep[u]-dep[v],n;x;)
n=log2(x),u=f[u][n],x-=(1<<n);
//for(int i=log2(n);~i;--i)
//if(dep[f[u][i]]>=dep[v]) u=f[u][i];
if(u==v) return v;
for(int j=log2(n);~j;--j)
if(f[u][j]!=f[v][j]) u=f[u][j],v=f[v][j];
return f[u][0];
}
void Add(int x,int y){
G[x].push_back(y);
G[y].push_back(x);
}
main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>s;
for(int i=1,x,y;i<n;++i)
cin>>x>>y,Add(x,y);
dfs(s,0),init();
for(int a,b;m--;)
cin>>a>>b,cout<<LCA(a,b)<<'\n';
}
```
by cat_lover1 @ 2024-04-04 15:16:00