Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)


Given a tree with $N$ vertices and $N - 1$ edges. Each vertex has a single letter $C_i$. Given a string $S$, you are to choose two vertices A and B, and make sure the letters catenated on the shortest path from A to B is exactly S. Now, would you mind telling me whether the path exists?


The first line is an integer T, the number of test cases.
For each case, the first line is an integer $N$. Following $N - 1$ lines contains two integers a and b, meaning there is an edge connect vertex a and vertex b.
Next line contains a string C, the length of C is exactly $N$. String C represents the letter on each vertex.
Next line contains a string S.
$1 \leq T \leq 200$, $1 \leq N \leq 10^4$, $1 \leq a, b \leq N$, $a \neq b$, $|C| = N$, $1 \leq |S| \leq 10^4$. String C and S both only contain lower case letters.


First, please output "Case #k: ", k is the number of test case. See sample output for more detail.
If the path exists, please output “Find”. Otherwise, please output “Impossible”.

Sample Input

2 7 1 2 2 3 2 4 1 5 5 6 6 7 abcdefg dbaefg 5 1 2 2 3 2 4 4 5 abcxy yxbac

Sample Output

Case #1: Find Case #2: Impossible




2015 ACM/ICPC Asia Regional Shanghai Online