1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <vector>  5 using namespace std;  6 #define MAXN 10001  7 int n,fa[MAXN];  8 int indegree[MAXN];  9 int vis[MAXN]; 10 vector<int> hash[MAXN]; 11 struct Node{ 12    int v; 13    int next; 14    int id; 15 }edge[MAXN*4]; 16 int head[MAXN],cnt; 17 int ances[MAXN],ans[MAXN];//祖先 18 void init(){ 19   memset(head,-1,sizeof(head)); 20   memset(ans,-1,sizeof(ans)); 21   cnt=0; 22 } 23 void add(int u,int v,int w){ 24     edge[cnt].v=v; 25     edge[cnt].id=w; 26     edge[cnt].next=head[u]; 27     head[u]=cnt++; 28      edge[cnt].v=u; 29     edge[cnt].id=w; 30     edge[cnt].next=head[v]; 31     head[v]=cnt++; 32 } 33  34 void init(int n){ 35     for(int i=0;i<=n;i++){ 36         fa[i]=i; 37         indegree[i]=0; 38         vis[i]=0; 39         ances[i]=0; 40         hash[i].clear(); 41        // Qes[i].clear(); 42     } 43 } 44 int find(int x){ 45    int s; 46    for(s=x;s!=fa[s];s=fa[s]); 47    while(s!=x){ 48      int temp=fa[x]; 49      fa[x]=s; 50      x=temp; 51    } 52    return s; 53 } 54 void unio(int x,int y){ 55     int fx=find(x),fy=find(y); 56     if(fx==fy) return ; 57      fa[fy]=fx; 58 } 59 void Tarjan(int u){ 60     ances[u]=u; 61     int i,size = hash[u].size(); 62     for(i=0;i<size;i++){ 63         Tarjan(hash[u][i]); 64         unio(u,hash[u][i]); 65         ances[find(u)]=u; 66     } 67     vis[u]=1; 68     for(int i=head[u];i!=-1;i=edge[i].next){ 69         int v=edge[i].v; 70         if(vis[v]==1){ 71             ans[edge[i].id]=ances[find(v)]; 72             return; 73         } 74     } 75  76     /*size = Qes[u].size(); 77     for(i=0;i<size;i++){ 78         if(vis[Qes[u][i]]==1){ 79             printf("%d\n",ances[find(Qes[u][i])]); 80             return; 81         } 82     }*/ 83 } 84 int main(){ 85     int t; 86     int i,j; 87     scanf("%d",&t); 88     while(t--){ 89         scanf("%d",&n); 90         init(n); 91         int s,d; 92         for(i=1;i<=n-1;i++){ 93             scanf("%d%d",&s,&d); 94             hash[s].push_back(d); 95             indegree[d]++; 96         } 97             scanf("%d%d",&s,&d); 98             init(); 99             add(s,d,1);100             add(d,s,1);101         for(j=1;j<=n;j++){102             if(indegree[j]==0){103                 Tarjan(j);104                 break;105             }106         }107         printf("%d\n",ans[1]);108     }109     return 0;110 }