代码如下：

#include <bits/stdc++.h>
using namespace std;

struct line{
	int next,to;
}g[500010];
int head[500010],dep[500010];
int f[500010][30];
int cnt=0;

void add ( int u , int v ){
	cnt++;
	g[cnt].next=head[u];
	g[cnt].to=v;
	head[u]=cnt;
}

void deal_first ( int father , int v ){
	//cout <<father<<" "<<v<<endl;
	dep[v]=dep[father]+1;
	for ( int i = 0 ; i <= 19 ; i++ ){
		f[v][i+1]=f[f[v][i]][i];
	}
	for ( int i = head[v] ; i != -1 ; i = g[i].next ){
		int go=g[i].to;
		if ( go==father ){
			continue;
		}
		f[go][0]=v;
		deal_first(v,go);
	}
	return;
}

int LCA ( int x , int y ){
	if ( dep[x]<dep[y] ){
		swap(x,y);
	} 
	for ( int i = 20 ; i >= 0 ; i-- ){
		if ( dep[f[x][i]]>=dep[y] ){
			x=f[x][i];
		}
		if ( x==y ){
			return x;
		}
		//cout <<"x:"<<x<<" y:"<<y<<endl;
		//cout <<f[x][i]<<endl;
	} 
	//cout <<"一层"<<endl;
	for ( int i = 20 ; i >= 0 ; i-- ){
		//cout <<"x:"<<x<<" y:"<<y<<endl;
		if ( f[x][i]!=f[y][i] ){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

int main (){
	memset(head,-1,sizeof(head));
	int xx,yy,zz;
	int n,m,root;
	
	cin >>n>>m>>root;
	
	while ( n>1 ){
		cin >>xx>>yy;
		if ( xx==yy )	continue;
		add(xx,yy);
		add(yy,xx);
		n--;
	}
	dep[0]=0;
	deal_first(0,root);
	for ( int i = 1 ; i <= m ; i++ ){
		cin >>xx>>yy;
		int lca=LCA(xx,yy);
		cout <<lca<<endl;
	}
	
	return 0;
}