描述

KEKE有一棵以1为根的树，这棵树有n个结点。
KEKE每次想询问你编号在[L,R]区间的lca。

格式

输入格式

第一行包含一个整数n，表示这棵树有n个结点。
第2行~第n行每行包含两个整数，表示一条树上的边。
接下来的一行包含一个整数q，表示有q组询问。
接下来q行每行包含两个整数L、R，表示询问。

输出格式

对于每个询问输出他们的公共lca。（若L==R输出本身）

样例

样例输入

10
1 2
1 8
2 3
2 7
3 4
3 5
3 6
8 9
8 10
5
4 6
4 7
3 7
9 10
7 9

样例输出

3
2
2
8
1

限制

每个测试点1s,256MB

提示

数据范围：1≤n,q≤2*10^5+5

Source

KEKE_046 && Bill_Yang