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
sorin_m2: 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

David: 2022-06-23 20:35:50

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

depressedboy: 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
sonmi451: 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.

zoro_swordsman: 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"!

sagsango: 2020-03-12 22:55:06

long long is giving WA.
Use unsigned long long to get AC.

nadstratosfer: 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.

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


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