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.

## Problem G: Iris's problem

Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 6 Solved: 2

[Submit][Status][Web Board]

## Description

## Input

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.

## Output

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 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
```

## HINT

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)

Anything about the Problems, Please Contact Admin:admin

All Copyright Reserved 2010-2013 ZJUT ONLINE JUDGE TEAM

GPL2.0 2003-2013 HUSTOJ Project TEAM