Optimal Spy Rendezvous

Ondrej and Edward are prisoners in the dreaded AQT base, which can be imagined as a tree of n rooms (in actual scenarios, n is 100), numbered from 0 to n-1. The tree structure means that there are n-1 corridors connecting these rooms, and any two rooms are connected by a unique simple path. The two spies are held in two distinct rooms, and they do not know each other's whereabouts.

The two spies have prearranged a strategy to rendezvous as quickly as possible. Their strategy is based on the following movement constraints:

• Ondrej may only take an action on odd minutes (i.e. minute 1, 3, 5, ...).
• Edward may only take an action on even minutes (i.e. minute 2, 4, 6, ...).

On his turn, a spy can choose either to stay in the current room or to move to one of its adjacent rooms (i.e. a room directly connected by a corridor).

If we denote by \(V(A, R, T)\) the room \(R\) in which spy \(A\) should be at minute \(T\) according to the predetermined plan, then a rendezvous occurs at the first time \(t(o,e)\) when \[ V(\text{Ondrej}, R, t(o,e)) = V(\text{Edward}, R, t(o,e)), \] that is, both spies find themselves in the same room at the same minute.

Let \(d(o,e)\) be the number of corridors in the unique shortest path between their initial rooms. A natural goal is to design the movement strategy in such a way that, over all possible choices of distinct initial rooms, the ratio \[ \frac{t(o,e)}{d(o,e)} \] is as small as possible.

It turns out that if both spies simply move along the unique shortest path between their starting positions (with Ondrej moving on odd minutes and Edward on even minutes), they will meet in exactly \(d(o,e)\) minutes. For example:

• If \(d(o,e)=3\), then the moves could be:
  • Minute 1 (odd): Ondrej advances one corridor.
  • Minute 2 (even): Edward advances one corridor.
  • Minute 3 (odd): Ondrej advances another corridor and they meet.
• If \(d(o,e)=4\), then after 4 minutes, they meet at the midpoint (each having moved 2 corridors).

Your task is to compute the meeting time given a tree and the initial positions of Ondrej and Edward, assuming they both move optimally along the unique shortest path between them. In other words, given the tree and two distinct starting rooms, output \(t(o,e) = d(o,e)\), the number of edges in the unique path between the two rooms.

Note: The input consists of multiple test cases. Although the story mentions 100 rooms, your program should work for any tree size \(n \ge 2\). You can assume that the given graph is always a tree.

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 50\)) representing the number of test cases.

For each test case:

1. The first line contains an integer \(n\) (\(2 \le n \le 100\)) representing the number of rooms.
2. The next \(n-1\) lines each contain two integers \(u\) and \(v\) (\(0 \le u, v \le n-1\)) indicating that there is a corridor connecting room \(u\) and room \(v\).
3. The last line of the test case contains two distinct integers \(o\) and \(e\) (\(0 \le o, e \le n-1\)), representing the initial rooms of Ondrej and Edward respectively.

You may assume that the given corridors form a tree.

outputFormat

For each test case, output a single line containing one integer: the meeting time \(t(o,e)\), which is equal to the shortest path distance \(d(o,e)\) between the two initial rooms.

sample

3
5
0 1
1 2
1 3
3 4
0 4
3
0 1
1 2
0 2
4
0 1
1 2
1 3
2 3

3
2
2

</p>