//为什么要攀登？因为山就在那里。
#include<bits/stdc++.h>
#define mrx 0x7f7f7f7f7f7f7f7f
#define int long long
using namespace std;
int n,m,root,fa[23][500010],deep[500010],id;
vector<int> p[500010];
void dfs(int now,int dad){
	deep[now]=deep[dad]+1;
	fa[0][now]=dad;
	for(auto to:p[now]) if(to!=dad) dfs(to,now);
}
int lca(int u,int v){
	if(deep[v]>deep[u]) swap(v,u);
	for(int i=22;i>=0;i--) if(deep[fa[i][u]]>=deep[v]) u=fa[i][u];
	if(v==u) return u;
	for(int i=22;i>=0;i--) if(fa[i][v]!=fa[i][u]) v=fa[i][v],u=fa[i][u];
	return  fa[0][u];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0); 
	cin>>n>>m>>root;
	for(int i=1;i<n;i++){
		int v,u;cin>>v>>u;
		p[v].push_back(u);
		p[u].push_back(v); 
	}
	dfs(root,0);
	for(int i=1;(1<<i)<=n;i++) for(int j=1;j<=n;j++) fa[i][j]=fa[i-1][fa[i-1][j]];
	for(int i=1;i<=m;i++){
		int v,u;cin>>v>>u;
		cout<<lca(v,u)<<'\n';
	}
	return 0;
}

这个代码TLE了，但是把fa[23][500010]的一二维对调就能通过