BGC TRUST IUPC 2012

Problem D

Chatgaiya Postman Problem

Nowadays, mail delivery through postal order has been increased a lot in Chatgao city and there is only one postman in the city. Every day he has to run through almost all the roads in the city. As he is very much lazy, he is tired of this and wants to make a plan to get rid of it.

According to his new plan, he will always start his mail delivery from a house and go through some distinct houses, will come back to the starting house and take rest, then he will go through another route of distinct houses and will come back to the starting house again. Note that the houses of the first and second round should also be different. He calls these types of routes dumbbell routes. Now he is curious about how many dumbbell routes are there in the city. As he is a lazy person he gives the job to find the number of dumbbell routes in the city Chatgao to you.

Formally, there are N houses . Available road connections between houses are also provided as input. A dumbbell route is a sequence of houses where

1. Every consecutive houses and (for ) are connected by a road

2. and for every other i, j pair

3. and

Find how many distinct dumbbell routes are there in the city. Two dumbbell routes will be considered same if they have same set of roads.

In the above example, there is only one dumbbell route. The routes 2-1-0-2-3-4-2 and 2-0-1-2-3-4-2 are same.

Input

Input starts with a positive integer, T (T ≤ 100) denoting the number of test cases. Each case starts with two integers, N (1 ≤ N ≤ 13) number of houses (indexed from 0 to N-1) and M (0 ≤ M ≤ N*(N-1)/2) number of roads in the city. Each of the next M lines contains two integers u and v (0 ≤ u, v < N, u ≠ v) meaning that there is a bidirectional road between two different house u and v. All the roads will be distinct.

Output

For each case, print the test case number, starting from 1, and the answer, number of dumbbell routes in the city. The answer will fit into 64-bit signed integer.

Sample Input	Output for Sample Input
2 5 6 0 1 1 2 2 0 2 3 3 4 4 2 6 7 0 1 1 2 2 0 2 3 3 4 4 5 5 3	Case 1: 1 Case 2: 0

Problemsetter: Shiplu Hawlader

Special Thanks: Md. Mahbubul Hasan