Spring Buzz

Description

With spring now here, the dogwood, apple, pear, and cherry trees will soon be in bloom. Busy bees will be harvesting the nectar from the flowering trees in the forest.

The bees are good at bookkeeping. For simplicity, they have numbered the flowering trees in their forest from 0 to n − 1. Instead of roaming the forest looking for the flowering trees, they just use paths recorded in the bee book. Each path in the bee book is a straight line between two of the flowering trees. (A bee may move along this path from one tree to another in either direction.)

Now the busy bees want to optimize their work. They have decided that they will choose specific flowering trees — ones with lots of flowers! — in which to build their hives (a tree per hive). After they have established these hive trees — collectively, the hive colony — they will only collect nectar from these hive trees. So they will remove any path from the bee book to a non-hive tree.

The bees rules for making such a hive colony as as follows.

1. The bees will choose at least two of the flowering trees to put hives.

2. They want to choose the hive trees in such a way that if one of the paths in the bee book (after pruning for just the hive trees) gets blocked — e.g., sometimes a bear will block a path to demand honey — it still remains possible to get from any one hive tree to another.

3. Because building a hive is a lot of work, they want to build as few hives as necessary.

Input

You are given the bee book of paths. Your task is to propose a new bee hive colony. Input starts with an integer T (T ≤ 50) denoting the number of test cases.

Each case starts with a blank line. The next line contains two integers n (2 ≤ n ≤ 500) and m (0 ≤ m ≤ 20000), where n denotes the number of flowering trees and m denotes the number of paths. Each of the next m lines contains two integers u and v (0 ≤ u, v < n, u ≠ v) which means that there is a path between trees u and v. Assume that there can be at most one path between trees u and v, and that a given path will not be in the input more than once.

Note that the dataset your program will be tested against is very big. Use decent I/O methods and data-structures.

Sample Input

3
3 3
0 1
1 2
2 0

2 1
0 1

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

Output

For each case, print “Case x: ” where x is the case number (start the numering of cases with 1) followed by the number of beehives in the proposed colony, or “impossible” if its impossible to find such a colony.

Sample Output

Case 1: 3
Case 2: impossible
Case 3: 3