说明

给定一棵树和两个不同的结点，求出他们最近的公共祖先父结点。已知该树有n个节点，标号1..n，标号为1的结点是该树的根。

输入格式

第1行输入一个整数n，代表结点数量（n≤100） 

第2行输入两个整数x，y，表示需要计算的结点 以下n-1行

每行两个整数a和b，结点a和b是父子关系，但不保证a是b的父

输出格式

x与y的最近公共祖先

样例

9
9 7
2 1
3 2
4 2
5 3
8 5
9 5
6 4
7 4

2

邻接表结构建树模板：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

深度优先遍历 —— 模板
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}