Mr. Xu is a student of CSE who is very curious in graph theory. In past years he solved different types of graph problems, now he faced a problem with graph theory please help Mr. Xu to solve this problem.
Mr. Xu defined his problem like this:
Give a graph with N vertices and E edges where N denotes the number of vertices and E denotes the number of bi-directional edges. This graph may contain one or more cycles, in graph theory a cycle means closed walk, consisting of a sequence of vertices starting and ending at the same vertex, with every two consecutive vertices in the sequence adjacent to each other in the graph.
Now if a vertex is part of only one simple cycle then we called this vertex is a Good vertex.
A simple cycle is a closed walk with no repetition of vertices or edges allowed, other than the repetition of the starting and ending vertex.
If a simple cycle contains more than two vertexes and all vertices are Good vertexes then we define this cycle as a Golden cycle.
Now he tries to find how many Golden cycles are containing in the given graph.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each test case contains two integers N (1 ≤ N ≤ 20000), E (1 ≤ E ≤ 50000).N denotes the number of vertices and E denotes the number of bi-directional edges. Each of the next E lines will contain two different integers u v (1 ≤ u, v ≤ n) denoting that there is an edge between u and v.
Output
For each case, print the case number and the total number of Golden cycles.
Sample
| Input | Output |
|---|---|
2 4 3 1 2 2 3 2 4 4 4 1 2 2 3 2 4 3 4 | Case 1: 0 Case 2: 1 |
