RT

#include<bits/stdc++.h>
using namespace std;
const int MCST=5e5+10,MLOG=18+2;
vector<int> G[MCST];
int anc[MCST][MLOG];
int dep[MCST];
int lg[MCST];
int n;
void dfs(int u,int pa){
	dep[u]=dep[anc[u][0]=pa]+1;
	for(int i=1;i<=lg[dep[u]];i++)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for(int i=0,v;i<G[u].size();i++){
		v=G[u][i];
		if(v^pa)
			dfs(v,u);
	}
	return;
}
int lca(int u,int v){
	if(dep[u]<dep[v])
		swap(u,v);
	while(dep[u]^dep[v])
		u=anc[u][lg[dep[u]-dep[v]]];
	for(int i=lg[dep[u]];i>=0;i--)
		if(anc[u][i]^anc[v][i])
			u=anc[u][i],v=anc[v][i];
	return anc[u][0];
}
int main(){
	int m,s;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1,x,y;i^n;lg[++i]=lg[i>>1]+1){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(s,s);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}
```cpp