题目传送门

#include<bits/stdc++.h>
using namespace std;
int n,m,s,u,v,d[500005],f[500005];
vector<int> g[500005];
int lca(int u,int v){
	if(d[u]<d[v])swap(u,v);
	while(d[u]!=d[v])u=f[u];
	while(u!=v){u=f[u],v=f[v];}
	return u;
}
void bfs(int s){
	queue<int> q;
	int vis[500005]={0};
	q.push(s);
	d[s]=vis[s]=1;
	f[s]=s;
	while(q.size()){
		int now=q.front();
		q.pop();
		for(int i=0;i<g[now].size();i++)
			if(!vis[g[now][i]]){
				vis[g[now][i]]=1;
				f[g[now][i]]=now;
				d[g[now][i]]=d[now]+1;
				q.push(g[now][i]);
			}
	}
}
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;
}
int main(){
	n=read(),m=read(),s=read();
	for(int i=1;i<n;i++){
		u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bfs(s);
	for(int i=1;i<=m;i++){
		u=read(),v=read();
		cout<<lca(u,v);
		putchar('\n');
	}
}