SP8849 IMITATE - Imitation

Iris is a student of ethology studying the animal behavior. She is interested by the imitation behavior of animals. Imitation is an advanced behavior whereby an individual observes and replicates another’s. Iris is such a good researcher that she builds a mathematical model to describe the body figure of animals. She describes the body as a number of joints. And the figure or the status of animal body can be denoted as a set of ordered pairs of two different joints. To study the imitation of the animals, Iris defines the correlation of joints. She defines the correlation as the transitive closure of the ordered pairs of body status with its reflexive pairs eliminated. That is to say, the correlation is an anti-reflexive relation. In this case, we could say that one body status is imitating the other one when the correlations of both body statuses are the same. For example, for the joint set {J1, J2, J3}. The first body status contains the ordered pair (J1, J2), (J2, J3). And the second body status contains the ordered pair (J1, J2), (J2, J3), (J1, J3). We could say that the first body status is imitating the other one because both of the correlation sets are (J1, J2), (J2, J3), (J1, J3) since the definition of the correlation is the transitive closure of body status. For a given body status, that is, a given set of ordered pairs of joints, Iris want to get another body status, which is imitating the given one. At the same time, the desired body status must contain the minimum number of ordered pairs or the maximum number of ordered pairs. Your task is to calculate the minimum number and the maximum number.

There are several test cases. The first line of the input contains a single integer denoting the number of test cases. There are about 100 test cases, but 90% of them are relatively small. For each test case, the first line contains two integers **N** and **M** where **N** is the number of joints of both the given body status and the desired body status, **M** is the number of ordered pairs of the given body status. (1

For each test case, output two integers denoting the minimum and maximum number of ordered pairs of the desired set. Two integers are separated by a single space.