There are N islands and M bridges. All the bridges are setup between two islands and to pass a bridge you have to give a toll of $1. The bridges are built in such a way that there is no more than one path among two islands. Now, you want to visit at least K different islands. You may choose the starting island of your choice, but you want to visit at least K different islands in minimum cost (starting island is considered to be already visited).
Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with two integers N, M (1 ≤ N ≤ 105, 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 ≤ 50000) denoting the number of queries. Each of the next q lines contains one integer K (1 ≤ K ≤ 105).
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
| Sample Input | Sample Output |
|---|---|
2 2 1 1 2 3 1 2 3 5 4 1 2 2 3 2 4 2 5 2 3 2 | Case 1: 0 1 impossible Case 2: 2 1 |
Notes
- Dataset is huge, use faster I/O methods.
- For the first case, for K = 1, which ever island we start with, we visit this. So without giving any toll we can visit one island. For K = 2, we choose island 1 to start. So we visit island 2 using the only bridge. So it costs $1. For K = 3, as there are only 2 islands in total so we cannot visit 3 islands.