1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib>10 # define MAXN 50000111 using namespace std;12 13 inline int get_num() {14     int k = 0, f = 1;15     char c = getchar();16     for(; !isdigit(c); c = getchar()) if(c == ‘-‘) f = -1;17     for(; isdigit(c); c = getchar()) k = k * 10 + c - ‘0‘;18     return k * f;19 }20 21 int n, m, s;22 int fa[MAXN], qx[MAXN], qy[MAXN], ans[MAXN], f[MAXN];23 vector <int> vec[MAXN], q[MAXN];24 25 inline int find(int x)26 {27     return x == fa[x] ? x : fa[x] = find(fa[x]);28 }29 30 inline void dfs(int u)31 {32     int i, v;33     fa[u] = u;34     for(i = 0; i < vec[u].size(); i++)35     {36         v = vec[u][i];37         if(f[u] != v) f[v] = u, dfs(v);38     }39     for(i = 0; i < q[u].size(); i++)40         if(f[v = u ^ qx[q[u][i]] ^ qy[q[u][i]]])41             ans[q[u][i]] = find(v);42     fa[u] = f[u];43 }44 45 int main()46 {47     int i, x, y;48     n = get_num();49     m = get_num();50     s = get_num();51     for(i = 1; i < n; i++)52     {53         x = get_num();54         y = get_num();55         vec[x].push_back(y);56         vec[y].push_back(x);57     }58     for(i = 1; i <= m; i++)59     {60         qx[i] = get_num();61         qy[i] = get_num();62         q[qx[i]].push_back(i);63         q[qy[i]].push_back(i);64     }65     dfs(s);66     for(i = 1; i <= m; i++) printf("%d\n", ans[i]);67     return 0;68 }