Nearest Common Ancestor

Given a rooted tree and two vertices on it, the nearest common ancestor (NCA) of the two vertices is defined as follows.

• The nearest common ancestor of two vertices is the deepest vertex (that is, the one closest to the two vertices) that has both of them as descendants. Here, every vertex is also considered to be its own ancestor.

For example, in the figure above, both vertex 4 and vertex 8 have 15 and 11 as descendants, but the deepest such vertex (the one closest to 15 and 11) is 4, so the nearest common ancestor is 4.

Given a rooted tree and two vertices, write a program that finds the nearest common ancestor of the two vertices.

The first line contains the number of test cases T.

Each test case is given as follows.

• The first line contains the number of vertices N in the tree. (2 ≤ N ≤ 10,000)
• Each of the next N-1 lines contains one edge of the tree, given as two integers A B, meaning that A is the parent of B. (A tree with N vertices always has exactly N-1 edges.) Every vertex is labeled with an integer between 1 and N.
• The last line contains the two vertices whose nearest common ancestor must be found.

For each test case, print the nearest common ancestor of the two given vertices on its own line.