关于Tarjan算法的讲解：https://www.cnblogs.com/JVxie/p/4854719.html

重点：

下面详细介绍一下Tarjan算法的基本思路：

1.任选一个点为根节点，从根节点开始。

2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。

3.若是v还有子节点，返回2，否则下一步。

4.合并v到u上。

5.寻找与当前点u有询问关系的点v。

6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。

模板基于的题目：POJ 1330

#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")

// #include <bits/stdc++.h>
#include <cstdio>
#include <vector>

using namespace std;
typedef pair<int, int>  P;
const int N = 10010;

vector<int> G[N];   // 存树
vector<P> Q[N];     // 存询问，first为点，second为此询问的编号
int used[N];        // 保存每个节点是否访问过
int deg[N];         // 存每个点的入度
int ans[N];         // 存每次询问的结果
int pre[N];         // 并查集

void init()    
{
    for(int i=0; i<N; i++)   // 初始化
    {
        used[i] = 0;    // 所有点初始化为未访问过的
        pre[i] = i;     // 并查集初始化
        ans[i] = 0;     // 所有结果初始化为0，因为点是从1开始的
        deg[i] = 0;     // 所有点的入读都初始化为0
        Q[i].clear();   // 清空询问
        G[i].clear();   // 清空树
        
    }
}

int find(int x)     // 并查集，寻找掌门人
{
    if(x == pre[x])
        return x;
    return pre[x] = find(pre[x]);
}
void join(int a, int b) // 并查集，合并两个点
{
    int fa = find(a);
    int fb = find(b);
    if(fa != fb)
        pre[fa] = fb;
}

void lca(int u)     // 最近公共祖先，u为根节点 
{
    if(G[u].size() == 0)    // 如果当前节点没有子节点，就标记此点一访问过
        used[u] = 1;
    for(int i=0; i < G[u].size(); i++)  // 如果此点有子节点，先向下递归访问子节点
    {
        lca(G[u][i]);
        join(G[u][i], u);   // 将子节点并入到父节点中
        used[u] = 1;        // 子节点访问过后标记此点已访问过
    }   
    for(int i=0; i < Q[u].size(); i++)
    {
        if(used[Q[u][i].first]) // 如果一对询问点中的另一个也访问过
        {
            ans[Q[u][i].second] = find(Q[u][i].first);
        }
    }
}

void solve(int n)
{
    for(int i=1; i <= n; i++)
    {
        if(deg[i] == 0)     // 根节点是入度为0的点
        {
            lca(i);
        }
    }
}


int main()
{

    int t;
    scanf("%d", &t);
    while(t--)
    {
        init();
        int n, m;
        int a, b;
        scanf("%d", &n);
        m = n -1;
        for(int i=0; i<m; i++)
        {
            scanf("%d %d", &a, &b); // a到b有一条边
            G[a].push_back(b);
            deg[b] ++;
        }

        int q = 1;  // 1组询问
        for(int i=1; i <= q; i++)
        {
            scanf("%d %d", &a, &b);
            Q[a].push_back(P(b, i));
            Q[b].push_back(P(a, i));
        }
        solve(n);
        for(int i=1; i <= q; i++)
        {
            if(ans[i] != 0)
                printf("%d\n", ans[i]);
            else 
                printf("Not Connect\n");
        }

    }


    return 0;
}