问题 21625 --J

21625: J

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

Given a simple connected graph, you can add at most one edge to it. Your task is to make the number of the cut edges of this new graph be as minimum as possible. Note that a simple graph is a graph without self loop and multiple edges.

输入

The first line contains only one integer T, which is the number of test cases.
Each test case starts with two integers’ n and m which means that this graph has n vertices and m edges. Then follow m lines describe the edges of this graph. Note that the index of the vertices is from 1 to n.

输出

For each test case, output the case number first, then output the number of the cut edges of the new graph, make sure that this number should be as minimum as possible.

样例输入

4
5 4
1 2
1 3
1 4
1 5
5 4
1 2
2 3
3 4
4 5
6 6
1 2
2 3
3 1
1 4
2 5
3 6
3 3
1 2
2 3
3 1

样例输出

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

提示


T<=20



N<=100000



M<=200000

来源

 

[提交][状态]