最近公共祖先，是指在有根树中，找出某两个节点 u 和 v 最近的公共祖先。（若  u为 v的祖先或者 v为 u的祖先，则 LCA(u,v) 就是作为祖先的那个节点）。

现在有一棵以 1为根的有根树，树上一共有 n个节点。现在有 m次查询，每次询问两个节点的 LCA。

如图所示的数据中

LCA(3,5)=1

LCA(5,4)=2

LCA(1,4)=1

LCA(2,5)=2

第 1 行：一个正整数 n ，表示树上节点的个数(1<=n<=100000)。 

第 2~n行：每行两个正整数u,v ，表示节点 u到节点 v有一条边。 

第 n+1 行：一个正整数 m ，表示查询的次数。 

第n+2~n+m+1行：每行两个正整数 a,b，表示要查询的两个节点的编号。(1<=a,b<=n) 

对于每个询问，输出一个正整数表示答案，并换行。