1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6 #define N 500010

 7 #define D 20

 8

 9 int n,m,root,len=0;

10 int last[N],fa[N][D],dep[N];

11 struct edge{int x,y,next;}a[2*N];

12

13 void ins(int x,int y)

14 {

15     a[++len].x=x,a[len].y=y;

16     a[len].next=last[x],last[x]=len;

17 }

18 void build(int x,int f)

19 {

20     fa[x][0]=f, dep[x]=dep[f]+1;

21     for (int i=1;i<=D && (1<<i)<=dep[x];i++)

22       fa[x][i]=fa[fa[x][i-1]][i-1];

23     for (int i=last[x];i!=-1;i=a[i].next)

24       if (a[i].y!=f) build(a[i].y,x);

25 }

26 int LCA(int x,int y)

27 {

28     if (dep[x]<dep[y]) {int t;t=x,x=y,y=t;}

29     if (dep[x]!=dep[y])

30       for (int i=D;i>=0;i--)

31         if (dep[x]>=(1<<i)+dep[y]) x=fa[x][i];

32     if (x==y) return x;

33     for (int i=D;i>=0;i--)

34       if (dep[x]>=(1<<i) && fa[x][i]!=fa[y][i])

35         x=fa[x][i],y=fa[y][i];

36     return fa[x][0];

37 }

38 int main()

39 {

40     scanf("%d%d%d",&n,&m,&root);

41     int x,y;

42     memset(last,-1,sizeof(last));

43     for (int i=1;i<n;i++)

44     {

45       scanf("%d%d",&x,&y);

46       ins(x,y),ins(y,x);

47     }

48     dep[0]=0, build(root,0);//由于是0，x,y之间的最大距离就是fa[x][i],(1<<i)<=dep[x]-dep[y]

49     while (m--)

50     {

51       scanf("%d%d",&x,&y);

52       printf("%d\n",LCA(x,y));

53     }

54     return 0;

55 }