## CAC - Cactus

no tags

In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph
G is a tree composed of all the vertices and some (or perhaps all) of the edges of G. Informally,
a spanning tree of G is a selection of edges of G that form a tree spanning every vertex. That is,
every vertex lies in the tree, but no cycles (or loops) are formed. On the other hand, every
bridge of G must belong to T (a bridge is an edge whose deletion increases the number of
connected components).
A spanning tree of a connected graph G can also be defined as a maximal set of edges of G that
contains no cycle, or as a minimal set of edges that connect all vertices. - Wikipedia
In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any
two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph
belongs to at most one simple cycle. Equivalently, every block (maximal subgraph without a
cut-vertex) is an edge or a cycle. - Wikipedia

In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some (or perhaps all) of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex. That is, every vertex lies in the tree, but no cycles (or loops) are formed. On the other hand, every bridge of G must belong to T (a bridge is an edge whose deletion increases the number of connected components).

A spanning tree of a connected graph G can also be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices. - Wikipedia

In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph belongs to at most one simple cycle. Equivalently, every block (maximal subgraph without a cut-vertex) is an edge or a cycle. - Wikipedia cactus graph

Your task in this problem is to count the number of ways you can convert a cactus graph to a spanning tree.

### Input

The first line of input will be the number of test cases. Each test case will start with a two numbers N and E where N is the number of vertices of the cactus graph, vertices are numbered from 1 to N, 3 <= N <= 81 and E is the number of edges in the graph, 2 <= E <= 120. The next E lines each one will have two numbers v and w and that means there is an edge between vertix v and w.

### Output

For each test case print “Case C: X” without quotes where C is the case number starting with 1 and X is the number of ways you can convert the given cactus graph to a spanning tree.

### Example

```Input:
2
3 3
1 2
2 3
1 3
5 5
1 2
2 3
2 4
3 4
4 5

Output:
Case 1: 3
Case 2: 3```

hide comments manav1310: 2018-09-01 11:35:36 can somebody find a problem in this code https://ideone.com/e.js/Q2KoeC Edelweiss: 2013-05-15 12:22:39 I'm sorry to have been suspicious of test data. I'm really really sorry... please excuse me... I'll do anything you want from mee... I've also miscalculated the maximum of the result :P Ashamed... Last edit: 2013-11-12 11:37:11 Jacob Plachta: 2013-05-14 16:18:24 @Federico: Ah, thanks - I miscalculated and thought I'd only need a signed long long. Federico LebrÃ³n: 2013-05-14 15:01:15 If it's any help, my bug was printing unsigned long long as %lld instead of %llu :s hossamyosef: 2013-05-14 07:59:57 this problem had been tested by about 30 teams at our contest!! hossamyosef: 2013-05-14 07:59:57 test data is correct ! Francky: 2013-05-14 07:59:57 As psetter don't give a quick answer, I hide the problem. @psetter : please answer, or fix the problem. Add a comment and the problem will be visible. Jacob Plachta: 2013-05-14 07:59:57 @Edelweiss: Agreed, this is pretty suspicious :) Edelweiss: 2013-05-14 07:59:57 Please make sure that all the test data is correct and then rejudge.

 Added by: hossamyosef Date: 2013-05-13 Time limit: 3s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: FCIS/ASU Local Contest 2013