가장 가까운 공통 조상

루트가 있는 트리(rooted tree)와 그 트리 위의 두 정점이 주어질 때, 두 정점의 가장 가까운 공통 조상(Nearest Common Ancestor, NCA)은 다음과 같이 정의됩니다.

• 두 정점의 가장 가까운 공통 조상이란, 두 정점을 모두 자손으로 가지는 정점들 중에서 깊이가 가장 깊은(즉 두 정점에 가장 가까운) 정점입니다. 이때 각 정점은 자기 자신의 조상이기도 한 것으로 봅니다.

예를 들어 위 그림에서 15와 11을 모두 자손으로 가지는 정점으로는 4와 8이 있지만, 그중 깊이가 가장 깊은(15와 11에 가장 가까운) 정점은 4이므로 가장 가까운 공통 조상은 4입니다.

루트가 있는 트리와 두 정점이 주어질 때, 두 정점의 가장 가까운 공통 조상을 구하는 프로그램을 작성하세요.

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스는 다음과 같이 구성됩니다.

• 첫째 줄에 트리를 구성하는 정점의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)
• 다음 N-1개의 줄에는 트리의 간선 정보가 한 줄에 하나씩 주어집니다. 각 줄에는 두 정수 A B가 주어지며, 이는 A가 B의 부모라는 뜻입니다. (정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다.) 모든 정점은 1 이상 N 이하의 정수로 번호가 매겨집니다.
• 마지막 줄에는 가장 가까운 공통 조상을 구할 두 정점의 번호가 주어집니다.

각 테스트 케이스마다 주어진 두 정점의 가장 가까운 공통 조상을 한 줄에 하나씩 출력합니다.