E	Kisu Pari Na 2

So, it's learning time!! Suppose a word consisting of only 0 and 1 is called good if there is no adjacent one in the word. We are asked to find good words of length n. Now how to solve this problem? Let's get our hand dirty and try to find the number of good words for several values of n.

Value of n	Good Words	Number of Good words
1	0, 1	2
2	00, 01, 10	3
3	000, 001, 010, 100, 101	5
4	0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010	8

So, do you find any pattern? The numbers looks like Fibonacci numbers and yes it is Fibonacci number sequence. But the question is why it turned out to be Fibonacci sequence? Suppose we put 0 at the first position. Our constraint is not to put two adjacent ones. So we may fill up the remaining n-1 places as we like except the condition that there cannot be any adjacent ones. Now if we put 1 at the first position then? Well as we cannot put two adjacent ones, so the second position must be filled by a 0. And following the previous argument rest of the positions can be filled up by as we like except the condition of adjacent ones. So if we denote the number of good words of n length is W_n then W_n = W_(n-1)+ W_(n-2) which is of course the recurrence formula of Fibonacci number. And the base cases of this sequence are almost same as Fibonacci number as well.

When I gave this analysis to Mr. Oh he said, "Uh! Come on, this is a very naïve problem, if you are so much intelligent then solve this one: There are N islands and M bridges. All the bridges are setup between two islands and to pass a bridge you have to give toll of $1. The bridges are built in such a way that there is not more than one path among two islands. Now, you have to visit at least K different islands. You may choose starting island of your choice, but you have to visit at least K different islands in minimum cost. (Starting island is considered to be already visited)"

Input

The first line of input will contain T (≤ 10) denoting the number of cases.

Each case starts with two integers N, M (1 ≤ N ≤ 10000, 0 ≤ M < N). Each of the next M lines contains two integers u v (1 ≤ u, v ≤ N, u ≠ v) meaning that there is a bridge between island u and v. No bridge will be reported more than once.

The next line contains an integer q (1 ≤ q ≤ 10000) denoting the number of queries. Each of the next q lines contains one integer K (1 ≤ K ≤ 10000).

Output

For each case, print the case number first. Then for each query print the minimum amount of toll you need to pay to visit at least K different islands. If it is not possible, print "impossible".

Sample Input

Output for Sample Input

2 1

1 2

5 4

1 2

2 3

2 4

2 5

Case 1:

impossible

Case 2:

Note

For case 1:

1. For K = 1, which ever island we start with, we visit this. So without giving any toll we can visit one island.

2. For K = 2, we choose island 1 to start. So we visit island 2 using the only bridge. So it costs $1.

3. For K = 3, as there are only 2 islands in total so we cannot visit 3 islands.

Problem Setter: Md. Mahbubul Hasan, Special Thanks: Jane Alam Jan