Beehives

Bees are among the most diligent insects. To gather nectar and pollen from flowers, they rely on the trees of the forest. To keep their work simple, the bees have numbered the $n$ trees from $0$ to $n-1$. Instead of roaming the whole forest, they use only a fixed list of routes. Each route connects two trees, and the bees can travel it in either direction (in a straight line from one tree to the other). They never use a route that is not on the list.

As their techniques advanced, the bees changed the way they work. Rather than hovering over every tree in the forest, they decided to target only certain trees rich in flowers. So they plan to build new hives on some of those target trees. Once all the hives are built, the bees will gather food only from trees that have a hive, and they will delete some routes from the list so they never go to a tree without a hive; that is, only the routes between hive trees remain.

Now the bees want to build the hives. These hives must be such that, even if any single one of the routes is cut (a bird or animal on that route might disturb the bees), the bees can still travel between all hives using the remaining routes.

Because building a hive takes a lot of effort, the bees want to place hives on at least two trees while keeping their number as small as possible. Using the given trees and routes, propose a new colony of hives.

The first line contains an integer $T$ ($T \le 50$), the number of test cases.

Each case begins with one blank line. The next line contains two integers $n$ ($2 \le n \le 500$) and $m$ ($0 \le m \le 20000$), the number of trees and the number of routes. Each of the following $m$ lines contains two integers $u$ and $v$ ($0 \le u, v < n$, $u \ne v$), denoting a route between tree $u$ and tree $v$. There is at most one route between any pair of trees, and no route is given more than once.

For each case, print Case X: (where X is the case number) followed by the number of hives in the proposed colony. If no such colony can be formed, print impossible instead of a number.

The input data is large. Use fast input/output.