ORZ
P3379

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
namespace wzl{
int n,m,s;
const int maxnm = 5e5 + 1, logn = 20;
int head[maxnm]={}, to[maxnm*2]={}, nxt[maxnm*2]={}, dep[maxnm]={}, f[maxnm][logn];
int cnt = 0;
inline void add_edge(int u,int v){
	to[++cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
}
void dfs(int rot,int fa){
	dep[rot] = dep[fa] + 1;
	for(int i = 1; i <= logn; ++i)
		f[rot][i] = f[ f[rot][i-1] ][i-1];
	for(int i = head[rot]; i != -1; i = nxt[i]){
		int v = to[i];
		if(v != fa){
			f[v][0] = rot;
			dfs(v,rot);
		}
	}
	
}
int Lca(int x,int y){
	if(dep[x] < dep[y]) swap(x,y);
	for(int i = logn; i >=1; --i){
		if(dep[ f[x][i] ] >= dep[y]) x = f[x][i];
		if(x == y) return x; // ?
	} 
	for(int i = logn; i >= 0; --i){
		if(f[x][i] != f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
void main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m>>s;
	for(int i = 0; i <= n; ++i) head[i] = -1;
	for(int i = 1; i < n; ++i){
		int u,v;
		cin>>u>>v;
		add_edge(u,v); add_edge(v,u);
	} 
	
	dfs(s,0);
	for(int i = 0; i <= n; ++i)cout<<head[i]<<' ';
	cout<<"\n\n\n";
	for(int i = 1; i <= n; ++i){
		cout<<i<<":";
		for(int j = 0; j <= logn; ++j){
			cout<<f[i][j]<<' ';
		}
		cout<<'\n'; 
	} 
	do{
		int a,b;
		cin>>a>>b;
		cout<<Lca(a,b)<<'\n';
	}while(--m);
	return ;
} 
}


int main(){
	wzl::main();	
	return 0;
}