题目背景

"亲情树"是一款家族寻根游戏。

在游戏中，每个家族成员都有一个编号，编号为 $1$ 的成员是整个家族的祖先。 游戏会给出成员之间的亲子关系，然后提出一些"亲情挑战"：

给定两个家族成员的编号，找到他们最近的共同祖先。

例如，小 A 和小 B 都有同一个曾祖父，这个曾祖父就是他们最近的共同祖先。

现在请你来通关这个游戏。

题目描述

给定一棵有 $n$ 个节点的树，节点编号为 $1 \sim n$，根节点为 $1$。

有 $m$ 次询问，每次询问给出两个节点 $u$ 和 $v$，求它们的最近公共祖先（Lowest Common Ancestor, LCA）。

最近公共祖先：节点 $u$ 和 $v$ 的公共祖先中深度最大的那个。

输入格式

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

接下来 $n-1$ 行，每行两个整数 $u,v$，表示节点 $u$ 和 $v$ 之间有一条边。

接下来一行一个正整数 $m$，表示询问次数。

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

输出格式

输出 $m$ 行，每行一个整数，表示每次询问的结果。

样例输入

7
1 2
1 3
2 4
2 5
3 6
3 7
3
4 5
4 6
2 6

样例输出

2
1
1

样例解释

树的形态如下：

      1
     / \
    2   3
   / \ / \
  4  5 6  7

• $4$ 和 $5$ 的 LCA 是 $2$
• $4$ 和 $6$ 的 LCA 是 $1$
• $2$ 和 $6$ 的 LCA 是 $1$

数据范围

$1 \le n \le 1000$，$1 \le m \le 100$，$1 \le u, v \le n$。