Problem21625--J

21625: J

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

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.

Input

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.

Output

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.

Sample Input Copy

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

Sample Output Copy

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

HINT

T<=20

N<=100000

M<=200000

Source/Category