E

Masud Rana Input: Standard Input Output: Standard Output

Masud Rana, A Daring Spy Of Bangladesh Counter Intelligence. He is in a new mission. There is a total n cities in Bangladesh. Each city is connected to all other by bidirectional roads. So there are total n * (n-1) / 2 bidirectional roads. Many of the roads are under control of evil powers. City a is safely reachable from city b, if there is a path from a to b containing only roads which are not under control of evil powers. There are m roads which are safe from evil powers. The mission of Masud Rana is to destroy the evil powers of some roads, and make sure that every city is safely reachable from all other.

Masud Rana chose a new strategy for this special mission. Every morning he selects a random city other than the city he stays in at that moment, and visit that city by direct connecting road, in the time of his visit by the road he destroys all evil power of that road if exists any, and makes that road safe. After reaching new city, he stays there till next morning. In the next morning he checks whether all cities are safely reachable from all others. If he is already done his mission ends, otherwise he repeats same strategy.

Let us number the cities by 1, 2, ... , n. Masud Rana is in city 1 when he starts his mission.

What is the expected number of days to finish the mission for Masud Rana.

Input

Input will starts with an integer T(T ≤ 100) which denotes the number of test case. Each case starts with two integer N(N ≤ 1 ≤ 30) and M(0 ≤ M ≤ N*(N-1)/2). Each of the next lines contains two integers a and b (1 ≤ a, b ≤ N) which means road connecting city a and b is safe.

Output

You have to output the expected number of days required for Masud Rana. Print the case number followed by the output. Look at the sample in/out for exact format. Upto 1E-6 error in your output will be acceptable.

2 3 1 2 3 4 1 2 3

Case 1: 1.0 Case 2: 3.5

---

Problem Setter: Md. Arifuzzaman Arif
Special Thanks: Manzurur Rahman Khan