g7-07666. 最近公共祖先 未做

给定一棵包含 $n$ 个结点的树，结点编号为 $1$ 到 $n$，其中 $1$ 号结点是根。

有 $q$ 次询问，每次给出两个结点 $u,v$，请求出它们的最近公共祖先（LCA），即同时是 $u$ 和 $v$ 的祖先、且深度最大的那个结点。

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $a,b$，表示结点 $a$ 与结点 $b$ 之间有一条边。

接下来一行包含一个整数 $q$。

接下来 $q$ 行，每行包含两个整数 $u,v$，表示一次询问。

输出共 $q$ 行，每行一个整数，表示对应询问中 $u$ 与 $v$ 的最近公共祖先编号。

输入：

5
1 2
1 3
2 4
2 5
4
4 5
3 4
4 2
1 1

输出：

2
1
2
1

$1\le n\le 2000$，$1\le q\le 2000$，$1\le a,b,u,v\le n$。输入保证是一棵树。