The annual masquerade ball has begun, and Dongdong is excited to participate.

The masks for this year's ball are custom-made by the organizers. Every attendee can choose a mask they like upon entry. Each mask has a unique ID, and the organizers inform the person wearing that mask of its ID.

To add an air of mystery to the ball, the organizers have divided the masks into $k$ ($k \ge 3$) categories. Using special technology, the ID of a mask is marked on it such that only a person wearing a mask of category $i$ can see the ID of a person wearing a mask of category $i+1$, and a person wearing a mask of category $k$ can see the ID of a person wearing a mask of category $1$.

Attendees do not know how many categories of masks there are, but Dongdong is particularly curious. He wants to calculate the number of categories himself, so he begins collecting information from the crowd.

The information Dongdong collects consists of which person (by mask ID) saw the ID of another mask. For example, the person wearing mask ID 2 saw the ID of mask 5. Dongdong also sees some IDs himself, and he adds this information based on his own mask ID.

Since not everyone can remember all the IDs they have seen, the information Dongdong collects is not guaranteed to be complete. Please calculate the maximum and minimum possible number of mask categories based on the information Dongdong has obtained. Since the organizers have stated that $k \ge 3$, you must also take this into account.

Input

The first line contains two integers $n$ and $m$, separated by a space, where $n$ is the total number of masks prepared by the organizers, and $m$ is the number of pieces of information Dongdong has collected.

The next $m$ lines each contain two integers $a$ and $b$, separated by a space, indicating that the person wearing mask $a$ saw the ID of mask $b$. The same pair $a, b$ may appear multiple times in the input.

Output

The output contains two numbers: the first is the maximum possible number of mask categories, and the second is the minimum possible number of mask categories. If it is impossible to divide all masks into at least 3 categories such that all information is satisfied, it is considered that Dongdong's information is incorrect, and you should output two -1s.

Examples

Input 1

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

Output 1

4 4

Input 2

3 3
1 2
2 1
2 3

Output 2

-1 -1

Constraints

For 50% of the data, $n \le 300, m \le 1000$. For 100% of the data, $n \le 100000, m \le 1000000$.