题目描述

给你一棵树，树以下列方式给出：

• 编号为 1 的节点为根；
• 输入第一行给出一个数 $n$，表示一共有 $n$ 个节点；
• 接下来 $n−1$ 行，每行给出两个数 $x,y(x≠y)$，表示 $x,y$ 之间有一条边。

接下来有 $m$ 组询问，每组询问有两个数 $x,y(x≠y)$, 你需要求出 $x,y$ 的最近公共祖先。

输入格式

见题面。

输出格式

输出共 $m$ 行，每行 1 个数表示每次询问答案。

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

1
1
3

数据规模

对于所有数据，保证 $1≤n,m≤100000,1≤x,y≤n,x≠y$。