提示: 欢迎访问OurACM平台。
Problem 1997 How Many MST

Accept: 34    Submit: 103
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

MST is the abbreviation of “Minimum Spanning Tree”. Given a connected, undirected graph, a spanning tree of that graph is a sub graph which is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.

You are given an undirected graph and expected to calculate how many MST the graph has.(Two MST are considered different if at least one edge different!)

Input

The first line is one integer T indicates the number of the test cases. (T <= 30)

Then for every case, the first has two integers N and M, indicates the number of vertices and the number of edges. (2 <= N <= 5, 0 <= M <= 20)

Then follows M lines, every line has three integers Ai, Bi and Ci, indicate there is one edge between Ai and Bi whose value is Ci. (0 <= Ai, Bi < N, 0 <= Ci <= 100, Ai! = Bi) You may assume that there is at most one edge between any two vertices.

Output

Output one line.

First output “Case idx: ”, here idx is the case number count from 1.

Then output how many MST the graph has.

Sample Input

3 3 3 0 1 1 1 2 1 0 2 1 3 1 0 1 2 3 3 0 1 1 1 2 1 0 2 2

Sample Output

Case 1: 3 Case 2: 0 Case 3: 1

Source

FOJ有奖月赛-2010年12月

Submit  Back  Status  Discuss