```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m, rt;
int h[N], e[N], ne[N], cnt;
int son[N], si[N], fa[N], dep[N], top[N];
void add(int u, int v) {
e[++ cnt] = v, ne[cnt] = h[u], h[u] = cnt;
}
void dfs1(int u, int ff) {
fa[u] = ff, si[u] = 1, dep[u] = dep[ff] + 1;
for(int i = h[u]; i; i = ne[i]) {
int v=e[i];
if(v == ff) continue;
dfs1(v, u); si[u] += si[v];
if(si[son[u]] < si[v]) son[u] = v;
}
}
void dfs2(int u, int topf) {
top[u] = topf;
if(son[u]) dfs2(son[u], topf);
for(int i = h[u]; i; i = ne[i]) {
int v=e[i];
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int LCA(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
return dep[x] < dep[y] ? x : y;
}
int main() {
scanf("%d%d%d", &n, &m, &rt);
for(int i = 1; i < n; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
dfs1(rt, 0);
dfs2(rt, rt);
for(int i = 1; i <= m; ++ i) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", LCA(x, y));
}
return 0;
}
```
by I_AK_IOI_2357 @ 2024-02-01 12:16:51