TLE+MLE

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <string>
using namespace std; 
int n,m,s,u,v,cnt,a,b;
struct E{int ne,to;}edge[500000+5];
int f[500000+5][20+5],dep[500000+5],head[500000+5];
void add(int u,int v){
	cnt++;
	edge[cnt].to=v;
	edge[cnt].ne=head[u];
	head[u]=cnt;
}
void dfs(int now,int fa){
	dep[now]=dep[fa]+1;
	f[now][0]=fa;
	for(int i=1;(1<<i)<=dep[now];i++) f[now][i]=f[f[now][i-1]][i-1];
	for(int i=head[now];i;i=edge[i].ne){
		if(edge[i].to!=fa) dfs(edge[i].to,now);
	}
}
int lca(int a,int b){
	if(dep[a]>dep[b]) swap(a,b);
	for(int i=20;i>=0;i--){
		if(dep[b]-(1<<i)>=dep[a]) b=f[b][i];
	}
	if(a==b) return a;
	for(int i=20;i>=0;i--){
		if(f[a][i]==f[b][i]) continue;
		else a=f[a][i],b=f[b][i];
    }
	return f[a][0];
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n-1;i++){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dep[s]=1;
	dfs(s,0);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	
	return 0;
}