LCA

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+12;
int n,m,s,head[N],cnt,fa[N][22],dep[N];
struct Edge{
  int v,nex;
}edge[N<<1];

void add(int u,int v)
{
  edge[++cnt]=(Edge){v,head[u]};
  head[u]=cnt;
}

void dfs(int u)
{
  for(int i=head[u];i;i=edge[i].nex)
  {
    if(edge[i].v==fa[u][0]) continue;
    fa[edge[i].v][0]=u;
    dep[edge[i].v]=dep[u]+1;
    dfs(edge[i].v);
  }
}


int lca(int x,int y)
{
  if(dep[x]<dep[y]) swap(x,y);
  for(int i=21;~i;i--) if(dep[x]-(1<<i)>=dep[y]) x=fa[x][i];
  if(x==y) return x;
  for(int i=21;~i;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
  return fa[x][0];
}


int main(){
  cin>>n>>m>>s;
  int x,y;
  for(int i=1;i<n;i++)
  {
    cin>>x>>y;
    add(x,y),add(y,x);
  }
  dfs(s);
  for(int j=1;j<22;j++)
    for(int i=1;i<=n;i++)
    fa[i][j]=fa[fa[i][j-1]][j-1];
  while(m--)
  {

    cin>>x>>y;
    cout<<lca(x,y)<<endl;
  }

}