N개의 정점으로 이루어진 트리가 주어진다. 루트 노드는 항상 1번 노드이다.

이때 두 노드 u, v가 주어졌을 때, 두 노드의 가장 가까운 공통 조상(Lowest Common Ancestor, LCA)을 찾는 프로그램을 작성하시오.

가장 가까운 공통 조상이란, 두 노드 u, v를 하위 노드로 가지는 노드들 중에서 가장 깊이가 깊은 노드를 의미한다.

입력

첫째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N-1개의 줄에는 트리의 연결 상태를 나타내는 두 정수 u, v가 공백을 사이에 두고 주어진다.

이는 u번 노드와 v번 노드가 연결되어 있음을 의미한다.

그다음 줄에는 질문의 개수 Q가 주어진다. (1 ≤ Q ≤ 100,000)

다음 Q개의 줄에 걸쳐 가장 가까운 공통 조상을 구해야 하는 두 노드 u, v가 공백을 사이에 두고 주어진다.

출력

Q개의 줄에 걸쳐, 각 질문마다 입력으로 주어진 두 노드의 LCA 노드 번호를 출력한다.

제약 조건

1 ≤ N ≤ 100,000

1 ≤ Q ≤ 100,000

루트 노드는 1번이다.

모든 노드는 연결되어 있는 트리 구조임이 보장된다.

예제 입력 1

15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
3
8 11
12 15
4 5

예제 출력 1

2
3
2