题目描述
小杨家的族谱是一棵 个结点的树（结点编号 ..， 号结点为根），每个结点的深度是根到它路径上的边数，根的深度为 。现在给出树上的两个结点 ，请你求出它们的最近公共祖先（LCA）的编号：同时是 和 的祖先、且深度最大的那个结点。
输入格式
第一行一个整数 n。
接下来 n-1 行，每行两个整数 x, y，表示结点 x 与 y 之间有一条边。
最后一行两个整数 u, v，表示询问的两个结点。
输出格式
一行一个整数，表示 u 与 v 的最近公共祖先编号。
样例输入
7
1 2
1 3
2 4
2 5
3 6
3 7
4 6
样例输出
1
样例解释
4 的祖先链是 4 -> 2 -> 1，6 的祖先链是 6 -> 3 -> 1。两者公共祖先只有 1，因此 LCA(4,6)=1。
数据范围
- 1 <= n <= 200000
- 1 <= u, v <= n