题目背景

LCA(Least Common Ancestors)，即最近公共祖先。对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）。

题目描述

给定一棵树和两个不同的结点，求出它们最近的公共祖先结点。

已知该树有n个结点，标号1~n，1是根。

输入格式

第1行输入一个整数n，代表结点数量(2≤n≤1000)；

第2行输入两个整数x，y，表示需要计算的结点；

以下n-1行，每行两个整数a和b，表示a是b的父亲。

输出格式

一个整数，代表x与y的最近公共祖先。

输入/输出样例

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

2

说明/提示

时间1000ms，内存256MiB