National Olympiad in Informatics, China, 2008

The annual masquerade ball has begun, and DongDong will be enthusiastically participating. This year's masks are specially tailored by the host. Each person going to the party can choose a mask of their liking before they enter. Each mask is labeled with a number, and the host will tell this number to the person wearing the mask.

To give the party a more mystifying atmosphere, the host has divided the masks into $k$ $(k\ge 3)$ types, and using special technology, he has also marked each mask with its corresponding number. Only people wearing type $i$ masks will be able to see the numbers of the people wearing type $i+1$ masks. People wearing type $k$ masks will be able to see the numbers of people wearing type $1$ masks.

Guests of the party will not know just how many types of masks there are in the party. However, this has made DongDong very curious, so he decided to calculate for himself how many types of masks there are. Thus, he starts collecting information from the crowd of people.

DongDong's information tells him which person wearing one mask can see which other people's mask numbers. For example, person number $2$ can see the mask number of person number $5$. DongDong will also see some mask numbers himself, and he will also use this to make his information more complete.

Since not everybody can just remember all of the numbers they have seen, DongDong's information is not guaranteed to be perfectly complete. Now you must calculate, based on DongDong's current set of information, the maximum possible and minimum possible number of types of masks there may be. This is assuming there is at least one person at the party wearing a mask of type $i$ for all $1\le i\le k$. Since the host has already announced that $k\ge 3$, you must take this extra information into consideration.

Input Specification

The first line of input contains two space-separated integers $n$ and $m$, representing the total number of people and the total number of pieces of information that DongDong has collected, respectively.
In the following $m$ lines, each line contains two space-separated integers $a$ and $b$, indicating that person $a$ can see the mask number of person $b$'s mask. Identical pairs of $a$, $b$ may appear multiple times in the input data.

Output Specification

Output two space-separated integers on one line. The first integer is the maximum possible types of masks there may be, and the second integer is the minimum possible types of masks there may be. If there is no way to divide the masks into at least $3$ types making the information complete, then DongDong has to believe that the information is erroneous. In this case, output -1 twice.

Sample Input 1

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

Sample Output 1

4 4

Sample Input 2

3 3
1 2
2 1
2 3

Sample Output 2

-1 -1

Constraints

For $50\mathrm{\%}$ of the test cases, $n\le 300,m\le 1000$;
For $100\mathrm{\%}$ of the test cases, $n\le 100000,m\le 1000000$.

Problem translated to English by Alex.