测试点链接\

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010, MAXM = 500010;
int n, m, s, fa[MAXN][21]={{0}}, dep[MAXN];
vector <int> edge[MAXN];


void dfs(int node, int father){
	dep[node] = dep[father] + 1;
	fa[node][0] = father;
	for (int i=1;i<=20;++i) {
		fa[node][i] = fa[fa[node][i-1]][i-1];
	}
	for (auto son : edge[node]){
		if (son != father) dfs(son, node);
	}
}


int lca(int node1, int node2){
	if (dep[node1] < dep[node2]) swap(node1, node2);
	if (node1 == node2) return fa[node1][0];
	for (int i=19;i>=0;i--){
		if (dep[fa[node1][i]] >= dep[node2]) {
			node1 = fa[node1][i];
		}
	}
	if (node1 == node2) return node1;
	for (int i=19;i>=0;i--){
		if (fa[node1][i] != fa[node2][i]){
			node1 = fa[node1][i];
			node2 = fa[node2][i];			
		}
	}
	return fa[node1][0];
}


int main(){
	cin>>n>>m>>s;
	for (int i=1;i<n;++i){
		int u, v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dep[0] = 0;
	dfs(s, 0);
	for (int i=1;i<=m;++i){
		int a, b;
		cin>>a>>b;
		cout<<lca(a, b)<<endl;
	}
	return 0;
}