A Gentlemen's Agreement

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 however 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 and 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
4 4
0 1
1 2
2 3
3 0
6 12
0 1
0 2
0 3
0 4
1 2
2 4
4 3
3 1
1 5
2 5
3 5
4 5
8 12
0 1
0 2
0 6
1 3
1 7
2 3
2 4
3 5
4 5
4 6
5 7
6 7

Sample output

2
2
3
2
6
4