/*

LCA(POJ 1330)

在线算法 DFS+ST

*/

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int MAXN=;

int rmq[*MAXN];//rmq数组，就是欧拉序列对应的深度序列

struct ST{

    int mm[*MAXN];

    int dp[*MAXN][];//最小值对应的下标

    void init(int n){

        mm[]=-;

        for(int i=;i<=n;i++){

            mm[i]=((i&(i-))==)?mm[i-]+:mm[i-];

            dp[i][]=i;

        }

        for(int j=;j<=mm[n];j++)

            for(int i=;i+(<<j)-<=n;i++)

            dp[i][j]=rmq[dp[i][j-]]<rmq[dp[i+(<<(j-))][j-]]?dp[i][j-]:dp[i+(<<(j-))][j-];

    }

    //查询[a,b]之间最小值的下标

    int query(int a,int b){

        if(a>b)swap(a,b);

        int k=mm[b-a+];

        return rmq[dp[a][k]]<=rmq[dp[b-(<<k)+][k]]?dp[a][k]:dp[b-(<<k)+][k];

    }

};

//边的结构体定义

struct Edge{

    int to,next;

};

Edge edge[MAXN*];

int tot,head[MAXN];

int F[MAXN*];//欧拉序列，就是dfs遍历的顺序，长度为2*n-1，下标从1开始

int P[MAXN];//P[i]表示点i在F中第一次出现的位置

int cnt;

ST st;

void init(){

    tot=;

    memset(head,-,sizeof(head));

}

//加边，无向边需要加两次

void addedge(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void dfs(int u,int pre,int dep){

    F[++cnt]=u;

    rmq[cnt]=dep;

    P[u]=cnt;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].to;

        if(v==pre)continue;

        dfs(v,u,dep+);

        F[++cnt]=u;

        rmq[cnt]=dep;

    }

}

//查询LCA前的初始化

void LCA_init(int root,int node_num){

    cnt=;

    dfs(root,root,);

    st.init(*node_num-);

}

//查询u,v的lca编号

int query_lca(int u,int v){

    return F[st.query(P[u],P[v])];

}

bool flag[MAXN];

int main(){

    int T;

    int N;

    int u,v;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        init();

        memset(flag,false,sizeof(flag));

        for(int i=;i<N;i++){

            scanf("%d%d",&u,&v);

            addedge(u,v);

            addedge(v,u);

            flag[v]=true;

        }

        int root;

        for(int i=;i<=N;i++)

            if(!flag[i]){

                root=i;

                break;

            }

        LCA_init(root,N);

        scanf("%d%d",&u,&v);

        printf("%d\n",query_lca(u,v));

    }

    return ;

}

/*

POJ 1330

LCA在线算法

*/

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

const int MAXN=;

const int DEG=;

struct Edge{

    int to,next;

}edge[MAXN*];

int head[MAXN],tot;

void addedge(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void init(){

    tot=;

    memset(head,-,sizeof(head));

}

int fa[MAXN][DEG];//fa[i][j]表示结点i的第2^j个祖先

int deg[MAXN];//深度数组

void BFS(int root){

    queue<int>que;

    deg[root]=;

    fa[root][]=root;

    que.push(root);

    while(!que.empty()){

        int tmp=que.front();

        que.pop();

        for(int i=;i<DEG;i++)

            fa[tmp][i]=fa[fa[tmp][i-]][i-];

        for(int i=head[tmp];i!=-;i=edge[i].next){

            int v=edge[i].to;

            if(v==fa[tmp][])continue;

            deg[v]=deg[tmp]+;

            fa[v][]=tmp;

            que.push(v);

        }

    }

}

int LCA(int u,int v){

    if(deg[u]>deg[v])swap(u,v);

    int hu=deg[u],hv=deg[v];

    int tu=u,tv=v;

    for(int det=hv-hu,i=;det;det>>=,i++)

        if(det&)

            tv=fa[tv][i];

    if(tu==tv)return tu;

    for(int i=DEG-;i>=;i--){

        if(fa[tu][i]==fa[tv][i])

            continue;

        tu=fa[tu][i];

        tv=fa[tv][i];

    }

    return fa[tu][];

}

bool flag[MAXN];

int main(){

    int T;

    int n;

    int u,v;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        init();

        memset(flag,false,sizeof(flag));

        for(int i=;i<n;i++){

            scanf("%d%d",&u,&v);

            addedge(u,v);

            addedge(v,u);

            flag[v]=true;

        }

        int root;

        for(int i=;i<=n;i++)

            if(!flag[i]){

                root=i;

                break;

            }

        BFS(root);

        scanf("%d%d",&u,&v);

        printf("%d\n",LCA(u,v));

    }

    return ;

}