Scary Bulls

A USACO Themed Problem by Eric Yang

Estimated Difficulty: USACO Silver / Codeforces 1600

Problem Statement

Bessie the cow is lost in Farmer John's farm, which can be represented as a series of $N$ barns $(1\leq N\leq4\cdot10^{5})$ numbered $1...N$ connected by $N-1$ bidirectional pathways. Bessie starts at room $K$ $(1\leq K\leq N)$ and wants to get to Farmer John's home, located at barn $1$. Each minute, Bessie can either do nothing or move to an adjacent room.

Scattered around the farm are $M$ bulls $(0\leq M\leq N)$, located in different barns. Each minute, these bulls always move to an adjacent barn that leads them closer to the Farmer John's house. One minute after reaching Farmer John's house, the bulls walk behind the barn to sleep.

However, Bessie has a fear of bulls, meaning that if Bessie and one or multiple bulls are present in a barn, including Farmer John's house, at the same minute, then Bessie will faint of shock. Note that bulls functionally disappear one minute after reaching Farmer John's house. If Bessie chooses to do nothing during a turn, she can hide in the corner, causing bulls to have no effect on her.

Determine the minimum number of minutes (the first move starts at minute $1$) for Bessie to reach Farmer John's house without fainting.

Input Format

The first line contains $T$, the number of testcases.

In each testcase:

The first line contains integers $N$, $M$, and $K$.

The next $N-1$ lines contain barns $u$ and $v$, indicating that there is a path between barns $u$ and $v$.

The next $M$ lines contain barn $x$, a room with a bull.

Output Format

Print the answer for all $T$ testcases. For each testcase, print "TESTCASE" (without the quotes) on the first line. On the next line, print the minimum minutes elapsed until Bessie reaches Farmer John's house (the first move can occur at minute $1$).

Sample Input

2
7 4 4
1 2
2 3
2 4
4 5
4 6
4 7
2
3
6
7
6 2 3
1 2
1 3
3 4
3 5
4 6
2
6

Sample Output

TESTCASE
4
TESTCASE
2

Output Explanation

For the first test case, Bessie can hide in the corner at times $1$ and $2$. Starting at time $3$, she can finally move all the way to Farmer John's house without interruptions, making her final move at $4$ minutes.