Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem G: Iris's problem

Problem G: Iris's problem

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 6  Solved: 2
[Submit][Status][Web Board]


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 gure of animals. She describes the body as a number of joints. And the gure 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 denes the correlation of joints. She denes the correlation as the transitive closure of the ordered pairs
of body status with its re exive pairs eliminated. That is to say, the correlation is an anti-reexive 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 T 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 < N < 1000, 0 < M < 10000)
Next M lines, each line denoting an ordered pair (Xi, Yi). The Xi and Yi are integers between 1 and N. Note that we consider the joints as the number between 1 and N.


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 whitespace.

Sample Input

3 3
1 2
2 3
1 3
3 3
1 2
2 3
3 1
9 9
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7

Sample Output

Case #1: 2 3
Case #2: 3 6
Case #3: 9 18


In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal. If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure will be a different relation. A relation R on a set X is transitive if, for all x, y, z in X, whenever xRy and yRz then xRz. Examples of transitive relations include the equality relation on any set, the "less than or equal" relation on any linearly ordered set, and the relation " x was born before y" on the set of all people. Symbolically, this can be denoted as: if x < y and y < z then x < z.

(From Wikipedia::transitive closure)

[Submit][Status][Web Board]