N (1<= N <=100000) perfect killers (we number them 1, 2, 3, ... N) meet at Blue Mary's house. Every killer has a kind of skill - cloak. No one can see them when they are cloaked - except only a small group of people, which will be discussed later.

We can group these killers into M (M >=3) groups, called group No.1, group No.2, group No.3, etc. If killer A is in group No. x and killer B is in group No. (X%M+1), A can see B even if B is cloaked. This prevent killers from doing some bad things without the risk of being punished.

To keep their identity secret, every killer keep cloaked during the party. After the party, Blue Mary asked everyone a question, "Which killers can you see in the party?" Although some killers forget some person they have ever seen during the party, Blue Mary collects extremely much information. Now she needs you help to determine the value of M, because no killer is willing to share this value with her.

Input

Ten test cases(given one after another, you have to process all!). For each test case:

The first line contains two integers N and E (1<= E<= 180000). E lines follow, each line contains two space-separated integers A and B - killer number A can see killer number B even if he is cloaked.

Output

For each test case, output one line:

If the information given is contradictory, output one line "-1 -1". Otherwise output the largest and the smallest possible value of M, separated by a single space.

Example

Input:
6 5
1 2
2 3
3 4
4 1
3 5
3 3
1 2
2 1
2 3
[and 8 test cases more]

Output:
4 4
-1 -1
[and 8 test cases more]

Warning: large input/output data, be careful with certain languages