树上LCA2

题目描述

给你一棵 $n$ 个节点的以 $1$ 号节点为根的树，节点的编号为 $1$ 到 $n$。现在有 $m$ 组询问，对于每组询问 $u, v$，请求出 $u$ 号节点和 $v$ 号节点的最近公共祖先。

输入格式

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

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

输入保证是一棵树。

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

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

输出格式

输出共 $m$ 行，对于每组询问，输出一行一个整数表示对应的两个点的最近公共祖先的编号。

样例输入

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

样例输出

1
1

数据范围

对于所有数据，保证 $1\leq n, m\leq 100000, 1 \le u, v \le n$。