1 #include <iostream> 2 #include <stdio.h> 3 #include <cstring> 4 #include <vector> 5 #define N 100005 6 using namespace std; 7 vector <int> vec[N] ; 8 vector <pair<int,int> > query[N]; 9 struct node{10     int first , second;11 }e;12 13 vector <node> query[N];14 15 int vis[N] , pre[N] , ans[N];16 int Find(int x){17     if(pre[x] == x){18         return x;19     }else{20         pre[x] = Find(pre[x]);21         return pre[x];22     }23 }24 void dfs(int u , int fa){25     26     pre[u] = u;27     vis[u] = 1;28     for(int i = 0 ; i < vec[u].size() ; i ++){29         int v = vec[u][i];30         if(v == fa) continue;31         dfs(v , u);32     }33     34     for(int i = 0 ; i < query[u].size() ; i++){35         int v = query[u][i].first;36         int id = query[u][i].second;37         if(vis[v] == 1){38             ans[id] = Find(v);39         }40     }41 42     pre[u] = fa;43 }44 45 int main(){46     int T;47     scanf("%d" ,&T);48     while(T --){49         int n , x, y;50         scanf("%d" , &n);51         for(int i = 0 ; i < n - 1 ; i ++){52             scanf("%d%d" , &x , &y);53             vec[x].push_back(y);54             vec[y].push_back(x);55             vis[y] = 1;56         }57         for(int i = 1 ; i <= n ; i ++ ){58             cout << i << "==========" << endl;59             for(int k = 0 ; k  <  vec[i].size() ; k ++){60                 cout << vec[i][k] << " ";61             }62             cout << endl;63         }64         int q;65         scanf("%d",&q);66         for(int i = 0 ; i < q ; i ++){67             scanf("%d%d" , &x , &y);68             query[x].push_back({y , i});69             query[y].push_back({x , i});70         }71         for(int i = 1 ; i <= n ; i ++){72             if(vis[i] == 0){73                 memset(vis , 0 ,sizeof(vis));74                 dfs(i , -1);75                 break;76             }77         }78         for(int i = 0 ; i < q ; i ++){79             printf("%d\n" ,ans[i]);80         }81     }82 }