我们根据能否看见建图，有向图边权设成1，然后我们转成无向图，
对于每条有向边连一条反边，边权是-1，然后从每个块中任意一个点开始
dfs，每个点有一个值，经过一条边到另一个点之后，用原来的点值和边权
更新新的点的点值，那么如果我们访问到了一个原来已经走过的点，那么我们
找到了一个环（可能是非环，就是一个点出两条有向边，然后又交在一点了），由于
数据是合法的，所以这样的非环的现在应该更新成的点值和原有的点值相等，如果不相等
的话，取差值的绝对值，就是这个环的长度。
那么我们对于所有块，每个块的环的长度都是种类数的倍数，所以取gcd就好了
还有一种情况就是没有环，全都是以链的形式存在的，对于这种形式，我们每个块
染色，然后找到每个块中点值最大的最小的差值就是最长链的长度。
无解的情况比较容易讨论，在此不再赘述。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
{$M 65536000}
//By BLADEVIL
var
n, m :longint;
pre, other, len :array[..] of longint;
last :array[..] of longint;
l :longint;
flag :array[..] of boolean;
size, father, key, tmin, tmax :array[..] of longint;
g :array[..] of longint;
ans1, ans2 :longint;
procedure swap(var a,b:longint);
var
c :longint;
begin
c:=a; a:=b; b:=c;
end;
function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
function gcd(a,b:longint):longint;
begin
if b>a then swap(a,b);
if b= then exit(a) else exit(gcd(b,a mod b));
end;
procedure connect(x,y,z:longint);
begin
inc(l);
pre[l]:=last[x];
last[x]:=l;
other[l]:=y;
len[l]:=z;
end;
procedure dfs(x:longint);
var
q, p :longint;
begin
flag[x]:=true;
q:=last[x];
while q<> do
begin
p:=other[q];
if len[q]= then father[p]:=x;
if not flag[p] then
begin
flag[p]:=true;
size[p]:=size[x]+len[q];
key[p]:=key[x];
dfs(p);
end else
begin
inc(g[]);
g[g[]]:=abs(size[x]+len[q]-size[p]);
if g[g[]]= then dec(g[]);
end;
q:=pre[q];
end;
end;
procedure init;
var
i :longint;
x, y :longint;
begin
read(n,m);
for i:= to m do
begin
read(x,y);
connect(x,y,);
connect(y,x,-);
end;
for i:= to n do father[i]:=-;
for i:= to n do if not flag[i] then dfs(i);
end;
procedure main;
var
i :longint;
begin
if g[]= then
begin
fillchar(flag,sizeof(flag),false);
for i:= to n do if (father[i]=-) and (key[i]=) then
begin
key[i]:=i;
dfs(i);
end;
for i:= to n do tmax[i]:=-maxlongint;
for i:= to n do tmin[i]:=maxlongint;
for i:= to n do
begin
tmax[key[i]]:=max(tmax[key[i]],size[i]);
tmin[key[i]]:=min(tmin[key[i]],size[i]);
end;
for i:= to n do if tmin[i]<>maxlongint then inc(ans1,tmax[i]-tmin[i]+);
if ans1< then
begin
writeln(-,' ',-);
exit;
end else
begin
writeln(ans1,' ',);
exit;
end;
end else
begin
ans1:=g[];
for i:= to g[] do
ans1:=gcd(ans1,g[i]);
if ans1< then
begin
writeln(-,' ',-);
exit;
end else
begin
ans2:=;
for i:= to ans1 do
if ans1 mod i= then
begin
ans2:=i;
break;
end;
if ans2= then ans2:=ans1;
writeln(ans1,' ',ans2);
end;
end;
end;
begin
init;
main;
end.