import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def dfs(u, fa):
# 预处理
deep[u] = deep[fa] + 1
p[u][0] = fa
for i in range(1, 21):
p[u][i] = p[p[u][i - 1]][i - 1]
for v in G[u]:
if v == fa: continue
dfs(v, u)
def lca(x, y):
if deep[x] < deep[y]:
x, y = y, x
for i in range(20, -1, -1):
if deep[p[x][i]] >= deep[y]:
x = p[x][i]
if x == y:
return x
for i in range(20, -1, -1):
if p[x][i] != p[y][i]:
x, y = p[x][i], p[y][i]
return p[x][0]
n = int(input())
G = [[] for i in range(n + 1)]
deep = [0] * (n + 1) # deep[u]表示节点u的深度
p = [[0] * 21 for i in range(n + 1)] # p[u][i]表示节点u往上走2^i到达的节点
for _ in range(n - 1):
u, v = map(int, input().split())
G[u].append(v)
G[v].append(u)
dfs(1, 0)
Q = int(input())
for _ in range(Q):
x, y = map(int, input().split())
print(lca(x, y))
暂无评论