Nearest Common Ancestor

Interview

Time limit1sMemory limit128 MB

Summary

Given a rooted tree and two nodes, find their nearest common ancestor for each test case.

Level: Medium4 of 10
Topics: Tree, DFS, Linked list
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples8

Example 1

Input

Expected output

4
3

Example 2
Input
```
1
2
1 2
1 2
```
Expected output
```
1
```
Example 3
Input
```
1
2
1 2
2 1
```
Expected output
```
1
```
Example 4
Input
```
1
3
1 2
1 3
2 2
```
Expected output
```
2
```
Example 5
Input
```
1
5
1 2
2 3
3 4
4 5
5 3
```
Expected output
```
3
```
Example 6
Input
```
1
3
1 2
1 3
2 3
```
Expected output
```
1
```
Example 7
Input
```
1
4
2 1
2 3
4 2
1 3
```
Expected output
```
2
```
Example 8
Input
```
2
4
1 2
2 3
3 4
4 2
3
3 1
3 2
1 2
```
Expected output
```
2
3
```