1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=500005;
4 inline void read(int &tmp)
5 {
6 int x=1;char c=getchar();
7 for(tmp=0;!isdigit(c);c=getchar()) if(c=='-') x=-1;
8 for(;isdigit(c);tmp=tmp*10+c-48,c=getchar());
9 tmp*=x;
10 }
11 struct edge{int to;edge *nex;}e[maxn<<1],*head[maxn];
12 int tot;
13 #define New(p) p=&e[++tot];
14 int n,T,root;
15 int deep[maxn],f[maxn][32];
16 inline void add(int x,int y) {edge *p;New(p);p->nex=head[x];p->to=y;head[x]=p;}
17 void dfs(int k)
18 {
19 for(edge *i=head[k];i!=NULL;i=i->nex)
20 {
21 if(!deep[i->to])
22 {
23 deep[i->to]=deep[k]+1;
24 f[i->to][0]=k;
25 dfs(i->to);
26 }
27 }
28 }
29 void init()
30 {
31 for(int j=1;(1<<j)<=n;++j)
32 for(int i=1;i<=n;++i)
33 if(f[i][j-1]) f[i][j]=f[f[i][j-1]][j-1];
34 }
35 int LCA(int a,int b)
36 {
37 if(deep[a]<deep[b]) swap(a,b);
38 int i;for(i=0;(1<<i)<=n;++i);--i;
39 for(int j=i;j>=0;--j)
40 if(deep[a]-(1<<j)>=deep[b]) a=f[a][j];
41 if(a==b) return a;
42 for(int j=i;j>=0;--j)
43 if(f[a][j]&&f[a][j]!=f[b][j]) a=f[a][j],b=f[b][j];
44 return f[a][0];
45 }
46 int main()
47 {
48 read(n),read(T),read(root);
49 for(int i=1,x,y;i<n;++i) read(x),read(y),add(x,y),add(y,x);
50 deep[root]=1;f[root][0]=0;
51 dfs(root);
52 init();
53 while(T--) {int a,b;read(a),read(b);printf("%d
",LCA(a,b));}
54 return 0;
55 }
