题目描述

给你一棵 $n$ 个节点的二叉树，节点的编号为 1 到 $n$，二叉树的根为 1 号节点。

读入 $u,v$，请求出 $u$ 号节点和 $v$ 号节点的最近公共祖先 （Lowest Common Ancestor）。

如果 $x$ 号节点既是 $u$ 号节点的祖先也是 $v$ 号节点的祖先，则称 $x$ 号节点是 $u$ 号节点和 $v$ 号节点的公共祖先 。

如果 $x$ 号节点是 $u$ 号节点和 $v$ 号节点的所有公共祖先中深度最深的，则称 $x$ 号节点是 $u$ 号节点和 $v$ 号节点的最近公共祖先 。

输入格式

第一行一个整数 $n$ 表示节点数。

接下来 $n$ 行，每行两个整数，第一个整数表示 $i$ 号节点的左儿子的编号，第二个整数表示 $i$ 号节点的右儿子的编号，如果某个数字为 0 表示没有对应的子节点。

输入保证是一棵二叉树。

最后一行两个整数 $u,v$ 表示要求最近公共祖先的两个节点的编号。

输出格式

输出一行一个整数，代表 $u$ 号节点和 $v$ 号节点的最近公共祖先。

4
0 2
3 4
0 0
0 0
3 4

2

数据规模

对于所有数据，保证 $2≤n≤1000,1≤u,v≤n$。