重链剖分求LCA

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

4
4
1
4
4

int lca(int u,int v) {
  while(top[u] != top[v]) {
    if(dep[top[u]] < dep[top[v]]) swap(u,v);
    u = fa[top[u]];
  }
  if(dep[u] < dep[v]) return u;
  else return v;
}

int n,m,rt;
struct node {
  int to;
  int nex;
} e[maxn];
int head[maxn],cnt;
void init() {
  for(int i=0; i<maxn; i++) head[i] = -1;
  cnt = 0;
}
void add(int u,int v) {
  e[cnt].to = v;
  e[cnt].nex = head[u];
  head[u] = cnt ++;
}
int fa[maxn],siz[maxn],son[maxn],dep[maxn],top[maxn];
void dfs1(int x) {
  siz[x] = 1;
  dep[x] = dep[fa[x]] + 1;
  for(int i=head[x]; ~i; i=e[i].nex) {
    int to = e[i].to;
    // fa[to] = x;
    if(to != fa[x]) {
      fa[to] = x;
      dfs1(to);
      siz[x] += siz[to];
      if(siz[to] > siz[son[x]]) son[x] = to;
    }
  }
}
void dfs2(int rt,int tp) {
  top[rt] = tp;
  if(son[rt]) dfs2(son[rt],tp);
  for(int i = head[rt]; ~i; i = e[i].nex) {
    int to = e[i].to;
    if(to != fa[rt] && to != son[rt]) dfs2(to,to);
  }
}
int lca(int u,int v) {
  while(top[u] != top[v]) {
    if(dep[top[u]] < dep[top[v]]) swap(u,v);
    u = fa[top[u]];
  }
  if(dep[u] < dep[v]) return u;
  else return v;
}
int main() {
  cin >> n >> m >> rt;
  init();
  for(int i = 1; i < n; i++) {
    int u=read,v=read;
    add(u,v);
    add(v,u);
  }
  dfs1(rt);
  dfs2(rt,rt);
  while(m --) {
    int u=read,v=read;
    cout<<lca(u,v)<<endl;
  }
  return 0;
}