可卡（无倍增朴素算法）：

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m, root;
vector<int> g[N];
int fa[N];
int depth[N];
inline int read()
{
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9')
   {
       if(ch == '-') w = -1; ch = getchar();
   }
   while(ch >= '0'&& ch <='9') s = s * 10 + ch - '0', ch = getchar();
   return s*  w;
}
inline void dfs(int x, int f)
{
    depth[x] = depth[f] + 1;
    fa[x] = f;
    for(int i = 0; i < g[x].size(); i ++)
    {
        if(g[x][i] != f) dfs(g[x][i], x);
    }
}
inline int lca(int x, int y)
{
    while(x != y)
    {
        if(depth[x] > depth[y])
        {
            x = fa[x];
        }
        else
        {
            y = fa[y];
        }
    }
    return x;
}
int main()
{
    cin >> n >> m >> root;
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b;
        a = read();
        b = read();
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(root, 0);
    while(m --)
    {
        int a, b;
        a = read();
        b = read();
        printf("%d\n", lca(a, b));
    }
    return 0;
}