备忘录

int get(int x, int y) {return dfn[x] < dfn[y] ? x : y;}
void dfs(int id, int f) {
  mi[0][dfn[id] = ++dn] = f;
  for(int it : e[id]) if(it != f) dfs(it, id); 
}
int lca(int u, int v) {
  if(u == v) return u;
  if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
  int d = __lg(v - u++);
  return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}
int main(){
  for(int i = 1; i <= __lg(n); i++)
  for(int j = 1; j + (1 << i) - 1 <= n; j++)
    mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
}

void dfs(int x,int y){
    f[x][0]=y;d[x]=d[y]+1;
    fo(__lg(d[x]))f[x][i]=f[f[x][i-1]][i-1];
    for(int i:node[x]) if(i!=y) dfs(i,x);
}
inline void lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    while(d[x]>d[y])x=f[x][__lg(d[x]-d[y])];
    if(x==y){write(x),putchar('\n');return;}
    for(int k=__lg(d[x]);k>=0;--k)
        if(f[x][k]!=f[y][k])x=f[x][k],y=f[y][k];
    write(f[x][0]);putchar('\n');return;
}
int main(){
    int a,b;n=read(),m=read(),s=read();
    fo(n-1)a=read(),b=read(),node[a].push_back(b),node[b].push_back(a);
    dfs(s,0);
    fo(m)a=read(),b=read(),lca(a,b);
}