CAC - Cactus

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

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

hide comments
2024-08-28 12:29:05
Just need to find all the cycle length in that graph , AC in one *.*
2024-06-04 23:47:22
3^40 should be the maximum (i.e. 81, 120, where all simple cycles are size of 3). So unsigned long long or long double should work.
2023-04-14 10:22:46
If you want to try the correct test from the picture above:
1
46 52
1 2
1 3
2 7
3 6
3 5
3 4
6 15
7 9
9 13
9 10
10 11
10 12
9 14
15 14
15 16
15 8
14 17
14 18
17 19
18 19
19 20
19 23
19 28
19 46
20 21
20 22
20 23
23 24
23 25
24 26
25 26
28 27
28 29
46 45
45 31
31 30
28 30
31 32
14 41
41 40
41 42
42 43
42 44
42 38
40 38
38 37
38 39
37 36
39 36
36 33
36 34
36 35

ans: 36864
2022-06-23 20:35:50 David
Here is the problem from the picture above!

1
46 51
1 3
2 3
3 4
3 5
5 8
8 11
8 9
8 10
11 12
12 13
12 16
13 14
13 15
12 7
7 6
6 4
11 20
20 19
20 21
21 22
19 17
18 19
22 24
22 23
24 25
23 25
25 26
25 27
25 28
11 29
11 30
29 31
30 31
31 39
39 40
40 41
41 42
41 43
43 44
44 45
44 46
44 31
30 32
32 33
33 30
32 34
32 35
33 37
37 38
38 36
36 33
2021-10-26 15:26:31
Some Points To Notice
1> Ans will always be greater than 1 if it contains at least one cycle or equal to one if given graph is tree only
2> Don't Forgot to clear graph and arrays after every testcase .

Also I have doubt
Why unsigned gives AC while long long gives wrong ans

Last edit: 2021-10-26 15:29:18
2021-02-09 01:03:23
I struggled for this way too long, so I hope I am able to help some desperate souls:
1) it is really true, you need unsigned long long or BigInteger for java (consider the input values for N and E!)
2) if the given graph is a spanning tree, return 1
3) if there are no ways to create a valid spanning tree, return 0
Without this knowledge, this task is 2% coding and 98% wondering why these output definitions are so low.
2021-02-03 17:59:42
hey guys, i don't know what should I print in the case of an invalid input, for example, N<3 or E>120
i always get the report "wrong answer"!
2020-03-12 22:55:06
long long is giving WA.
Use unsigned long long to get AC.
2019-12-23 22:34:03
Res = 1 if the graph is already a MST. WTF?! To each of you who WA'd on this stupidity and yet didn't bother to let others know, I wish you overtime on New Years eve.
2013-05-15 12:22:39 Edelweiss
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.