Masquerade Party

Time limit1sMemory limit256 MB

Summary

Given directed visibility edges between masks, find the maximum and minimum possible number of mask types k (at least 3) consistent with the observations.

Level: Hard8 of 10
Topics: Graph, Union-find, Implementation, Greedy
Solved: No attempts yet

Problem

The annual masquerade ball has begun, and DongDong will be joining in enthusiastically. 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 tells 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 ≥ 3) types, and using special technology he has also marked each mask with its type. Only people wearing type i masks can see the numbers of the people wearing type i + 1 masks. People wearing type k masks can see the numbers of people wearing type 1 masks.

Guests at the party do not know how many types of masks there are. This has made DongDong very curious, so he decided to work out for himself how many types of masks there are. So he starts collecting information from the crowd.

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

Since not everybody can 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. Since the host has already announced that k ≥ 3, you must take this extra information into consideration.

Input

The first line of input contains two space-separated integers n and m, the total number of masks and the total pieces of information DongDong has collected, respectively.

Each of the following m lines contains two space-separated integers a and b, indicating that the person wearing mask a can see the number of mask b. Identical pairs of a, b may appear multiple times in the input.

Constraints

n ≤ 100000, m ≤ 1000000.

Examples2

Example 1
Input
```
6 5
1 2
2 3
3 4
4 1
3 5
```
Expected output
```
4 4
```
Example 2
Input
```
3 3
1 2
2 1
2 3
```
Expected output
```
-1 -1
```