#include<bits/stdc++.h>
using namespace std;
#define ll int
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const ll N=500009;
int s,nE,d[N],f[N][20],hd[N],nxt[N],to[N],n,m;
void add(ll u,ll v){
	nE++;
	to[nE]=v;
	nxt[nE]=hd[u];
	hd[u]=nE;
}
void dfs(ll u,ll fa){
	d[u]=d[fa]+1;
	for(ll i=1;(1<<i)<=d[u];i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(ll i=hd[u];i;i=nxt[i]){
		ll v=to[i];
		if(v==fa) continue;
		f[v][0]=u; dfs(v,u);
	}
} 
ll lca(ll u,ll v){
	if(d[u]<d[v]) swap(u,v);
	for(ll i=19;i>=0;i--){
		if(d[f[u][i]]>=d[v]) u=f[u][i];
		if(u==v) return u;
	}
	for(ll i=19;i>=0;i--){
		if(f[u][i]!=f[v][i]){
			u=f[u][i];
			v=f[v][i];
		}
	}
	return f[u][0];
}
int main(){
	n=read(); m=read(); s=read();
	for(ll i=1;i<n;i++){
		ll u,v;
		u=read(); v=read();
		add(u,v); add(v,u);
	}
	dfs(s,0);
	for(ll i=1;i<=m;i++){
		ll a,b;
		a=read(); b=read();
		cout<<lca(a,b)<<endl; 
	}
    return 0;
}

上述代码MLE