RT(TLE)
RT(RE) (后面这个加了一些卡常的东西)

#include <bits/stdc++.h>
using namespace std;
const int N=500005;
const int MLOG=19;
int to[N*2],fi[N],ne[N],de[N],anc[N][MLOG+2],tot=-1,lg[N+2];
void link(int x,int y)  
{
	to[++tot]=y;ne[tot]=fi[x];fi[x]=tot;
}
void dfs(int cur,int fath)
{
	de[cur]=de[fath]+1;
	anc[cur][0]=fath;
	for(int i=1;i<=lg[de[cur]];++i) anc[cur][i]=anc[anc[cur][i-1]][i-1];
	for(int i=fi[cur];i;i=ne[i]) if(to[i]!=fath) dfs(to[i],cur);
}
int lca(int a,int b)
{
	//de[a]>=de[b]
	for(int i=lg[de[a]]-1;i>=0;--i) 
		if(de[anc[a][i]]>=de[b]) a=anc[a][i];
	if(a==b) return a;
	for(int i=lg[de[a]]-1;i>=0;--i) 
		if(anc[a][i]!=anc[b][i]) a=anc[a][i],b=anc[b][i];
	return anc[a][0];
	//return a;
}
int main()
{
	int n,m,s,x,y,a,b;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;++i) 
	  lg[i] = lg[i-1] + (1 << lg[i-1] == i); 
	for(int i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		link(x,y);link(y,x);
	}
	dfs(s,s);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",lca((de[a]>de[b]?a:b),(de[a]>de[b]?b:a)));
	}
	return 0;
}