masquerade

Problem Description

Rar the Cat is invited to a masquerade ball with N people. For convenience, the organisers of the ball have labelled the participants with a distinct ID from 1 to N.

Before the masquerade ball, the organisers have prepared K types of mask before hand and labelled from from type 1 to type K. These masks are special, if a person wears a mask of type x, he is able to see through people wearing mask of type (x % K) + 1. For example, if K = 3, those wearing mask 1 can see through mask 2, those wearing mask 2 can see through mask 3, and those wearing mask 3 can see through mask 1.

The organisers have pre-allocated the participants with 1 mask each. Each of the masks are one of the K types that was prepared before the ball. To ensure that there is a wide variety of different types of masks at the ball, the organisers have ensured that there are at least 3 types of masks at the event.

Rar the Cat and the other participants do not know how many types of masks there are at the event in total. They do not know the value of K. However, Rar the Cat is curious about the number of types of masks there are in the ball. Do note that if there are 5 masks prepared by the organiser (K = 5), but only 4 types of masks are in ball, Rar the Cat is interested to know that there are 4 types of masks in the ball.

To figure out the number of types of masks, Rar the Cat has gathered M pieces of information from the ball participants (including himself). Each piece of information is such that participant ID A can see through the mask of participant ID B. This means that if participant ID A has mask type x, participant ID B has mask type (x % K) + 1

Based on the above gathered information, Rar the Cat wants you to figure out the minimum and maximum number of types of masks in the ball. In addition, do note that you have to factor in that the organisers promised that there will be at least 3 types of masks at the event. In the event that it is not possible to have at least 3 types of masks at the event, you are to print "-1 -1" as the organisers have lied to you.

In addition, there is also a possibility that some other participants have lied to you and provided you with conflicting information. In this case, you are to print "-1 -1" as well.

Input

The first line of input contains 2 integers, N and M.

M lines will follow with A and B each. This means that participant A can see through the mask of participant B.

Output

Output 2 integers, the maximum number of types of masks followed by the minimum number of types of masks in the ball. In the event that the organisers or participants lied to you, print "-1 -1" instead.

Limits

For all testcases, 1 ≤ A, B ≤ N.

Subtask 1 (49%): 1 ≤ N ≤ 300, 1 ≤ M ≤ 1000.

Subtask 2 (51%): 1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁶.

Subtask 3 (0%): Sample Testcases.

Partial Scoring

43% of the marks will be awarded for only getting either the minimum or maximum correct.

Sample Testcase 1

Input

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

Output

4 4

Sample Testcase 2

Input

3 3
1 2
2 1
2 3

Output

-1 -1