문제

$N$개의 정점으로 이루어진 트리가 주어진다. 각 정점에는 $1$부터 $N$까지 번호가 매겨져 있고, 루트는 $1$번 정점이다.

이때 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• a b: $a$번 정점과 $b$번 정점의 가장 가까운 공통 조상(LCA, Lowest Common Ancestor)을 출력한다.

입력

첫째 줄에 $N$이 주어진다. ($2 \le N \le 100\,000$)

다음 $N-1$개의 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u$, $v$가 공백으로 구분되어 주어진다. ($1 \le u, v \le N; u \neq v$)

그 다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100\,000$)

다음 $Q$개의 줄에 걸쳐 각 쿼리를 의미하는 두 정수 $a$, $b$가 공백으로 구분되어 주어진다. ($1 \le a, b \le N; a \neq b$)

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

1
1
5
2
1