Shadow Shaman, the voodoo child, known as Rhasta, has returned from darkness and conquered the country of Dota once again with his sharpen wards. Now he wants to organize the country and divide it into several provinces so that he can control it in comfort. The country of Dota consists of N cities and M bidirectional roads, each of which connects two different cities. A cyclic route is a route of length R which starts and ends at the same city and consists of zero or more non-repeated intermediate cities, e.g. C1, C2, ..., CR, where Ci̸=Cj for1<i<R,1<j<R,i̸=jandC1=CR. A province is a maximal set of cities {C1, C2, . . . , Ck}, where at least one cyclic route contains both Ci and Cj (i ̸= j), for each 1 ≤ i ≤ k and 1 ≤ j ≤ k, i.e. two cities will be in same province if and only if they are in same cyclic route and the province is the largest possible set of such cities. A province can also consist of a single city, if the city is not in any cyclic route. Note that some cities can be part of more than one province. Length of a cyclic route is the number of bidirectional roads in the route. A cyclic route is inter- esting cyclic route if its length is an odd number. Rhasta wants his country to be an interesting one, so he wants all the cities of Dota should be part of at least one interesting cyclic route in every province it belongs. To make the country interesting, he wants to build new cities or bidirectional roads. Rhasta can add new cities or roads but he must maintain the following condition: After he adds new cities or roads the total number of existing province(s) should not be changed. Rhasta wants to make the country interesting but also wants to do this in minimal cost. What is the minimum number of new roads and cities Rhasta needs to build to make the country interesting? Input Input starts with an integer, T (T ≤ 20) denoting the number of test cases. Each case starts with two integers, N (1 ≤ N ≤ 10000) and M (0 ≤ M ≤ 30000). Each of the next M lines contains two integers u and v (0 ≤ u,v < N, u ̸= v) meaning that there is a bidirectional road between city u and v. Output For each case, print the test case number, starting from 1, and the minimum number of roads and cities, separated by a space. See the sample output for more details. If there are several possible answers, first minimize the number of roads to be built and then the number of cities. Explanation for Sample Case In the sample test case, the roads and cities are shown below. There are two provinces. They share city3 as a common node. Since city0, city1 and city2 are not part of any interesting cyclic route, we can add 1 road connecting city1 and city3 resulting into the following graph and fulfill Rhasta’s demand of making Dotaa interesting country!
2/2 Sample Input 1 67 01 12 23 30 34 53 45 Sample Output Case 1: 1 0