5.py

importsys
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정

n=int(input())

parent= [0] * (n+1) # 부모 노드 정보
d= [0] * (n+1) # 각 노드까지의 깊이
c= [0] * (n+1) # 각 노드의 깊이가 계산되었는지 여부
graph= [[] for_inrange(n+1)] # 그래프(graph) 정보

for_inrange(n-1):
a, b=map(int, input().split())
graph[a].append(b)
graph[b].append(a)

# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
defdfs(x, depth):
c[x] =True
d[x] =depth
foryingraph[x]:
ifc[y]: # 이미 깊이를 구했다면 넘기기
continue
parent[y] =x
dfs(y, depth+1)

# A와 B의 최소 공통 조상을 찾는 함수
deflca(a, b):
# 먼저 깊이(depth)가 동일하도록
whiled[a] !=d[b]:
ifd[a] >d[b]:
a=parent[a]
else:
b=parent[b]
# 노드가 같아지도록
whilea!=b:
a=parent[a]
b=parent[b]
returna

dfs(1, 0) # 루트 노드는 1번 노드

m=int(input())

foriinrange(m):
a, b=map(int, input().split())
print(lca(a, b))