match

Task

There are $M$ matches that cannot end in a draw. At the end of each match, one point is awarded to the winner. Determine a way to determine the winners of each match so as to obtain the lowest possible maximum score. In case of a tie, the solution in which the minimum score is as high as possible is required.

Input data

The input contains the number $T$ of tests on the first line. Each test case contains the following data:

The numbers $N$ of players and $M$ of matches on the first line, and on the following $M$ lines $2$ numbers each, representing the indices of two players who will play a match. If a pair appears several times in the file, it means that the $2$ players will play more matches against each other.

Output data

The output will contain the answers to the $T$ tests on separate lines, containing the minimum maximum score separated by a space from the maximum minimum score.

Constraints and clarifications

• $T \leq 25$
• $N \leq 50$
• $M \leq 200$
• For each of the $T$ tests, the $M$ lines describing the matches are randomly generated. That is, the two indices on each such line are chosen with uniform probability from the set of distinct non-zero natural number pairs smaller than or equal to $N$.

Example

stdin

1
5 5
1 2
1 3
1 4
2 3
4 5

stdout

1

Explanation

The first match is won by the first player, the second by the third, the third by the fourth, the fourth by the second, the fifth by the fifth - in such a way to obtain a minimum maximum score equal to $1$, and a maximum minimum score also equal to $1$.