该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵树和两个不同的结点，求出它们最近的公共祖先（LCA，Lowest Common Ancestor）结点。已知该树有 $n$ 个结点，标号为 $1 \sim n$。树的结构通过每个结点的父结点关系给出。

输入格式

第 1 行输入一个整数 $n$，代表结点数量（$n \leq 100$）。
第 2 行输入两个整数 $x$，$y$，表示需要计算最近公共祖先的两个结点。
以下 $n - 1$ 行，每行两个整数 $a$ 和 $b$，表示 $a$ 的父结点是 $b$。

输出格式

输出 $x$ 与 $y$ 的最近公共祖先 $root$。

样例

样例输入

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

样例输出

2

数据范围与提示

• 数据范围：结点数量 $n$ 满足 $1 < n \leq 100$，结点编号为 $1 \sim n$。