1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define N 100005 6 using namespace std; 7 vector 
         
           vec[N] ; 8 vector 
          
           
             > query[N]; 9 struct node{10 int first , second;11 }e;12 13 vector 
            
              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 }