The mayor of Madman City has decided that the city’s crossings need newer and better traffic lights. He has commissioned the company Light’s Inc. to remove the old and install the new traffic lights, because it is a very renowned company and one of the leading producers of traffic lights. The people in charge of this task (a mathematician and an engineer) have decided to minimize the ensuing chaos when the traffic lights are replaced, which entails that not all traffic lights can be replaced simultaneously. On the other hand they do not want to replace the traffic lights one at a time as that would take too long. So they decided that if they replaced the traffic lights at one intersection they would not replace the traffic lights at those intersections which were directly connected to the intersection where the traffic light was being replaced. Now the practical engineer was, of course, interested in the maximum number of intersections where the traffic lights could be replaced simultaneously, so he was looking for the largest set of intersections, where no two intersections in the set are connected by a road. The theoretical mathematician how- ever was interested in the number of different sets of intersections in which no subset containing two intersections is connected by a road and it is not possible to add another road without violating the previous condition. Input The first line contains the number of cities which are to be processed. The following lines contain the descrition of the cities. A city consists of a number of intersections and of a number of roads which connect the intersections. The number of intersections i, 1 ≤ i ≤ 60 and the number of roads r, 1 ≤ r ≤ 3600 are on a line. The intersections are numbered from 0 . . . i−1. The following r lines contain the description of the roads. The description of a road consists of the two intersections it connects. No intersections will be connected directly by two different roads. Furthermore the graph representing the city’s network of roads will be connected. Output For each each city, output the number of sets of intersections, where no two intersections in the set are connected by a road and it is not possible to add another intersection to the set without violating the first condition, on the first line. Print the number of intersections in the largest set on the second line. Sample Input 3 44 01 12 23 30 6 12 01 02 03 04 12
2/2 24 43 31 15 25 35 45 8 12 01 02 06 13 17 23 24 35 45 46 57 67 Sample Output 2 2 3 2 6 4