/*
分三种情况
1 有环：找环长的gcd作为max gcd的超过2的最小因子作为min
2 树：所有最长链的和作为max 3为min （最长链≥3）
3 两条相交链：找出所有的这样的两条链的差 同1求
显然第三种不好处理 看了别人的做法是+反向-1的边 1 3就能合并了.
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 1000010
#define pa pair<int,int>
using namespace std;
int n,m,num,head[maxn],dfn[maxn],topt;
int c[maxn],sum,Gcd,ans,maxx,minn,x,y,d[maxn];
bool f[maxn];
struct node
{
int v,pre,t;
}e[maxn],ei[maxn];
int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}
int abs(int a)
{
return a<?-a:a;
}
void Add(int from,int to,int dis)
{
num++;e[num].v=to;
e[num].t=dis;
e[num].pre=head[from];
head[from]=num;
}
void Tarjan(int x)
{
dfn[x]=++topt;f[x]=;
for(int i=head[x];i;i=e[i].pre)
{
int v=e[i].v;
if(f[v]==)d[v]=d[x]+e[i].t,Tarjan(v);
else c[++sum]=abs(d[x]-d[v]+e[i].t);
}
}
int Get_gcd()
{
Gcd=c[];
for(int i=;i<=sum;i++)
Gcd=gcd(Gcd,c[i]);
return Gcd;
}
int Get_min()
{
int tmp=Gcd+;
for(int i=;i<=Gcd;i++)
if(Gcd%i==)
tmp=min(tmp,i);
if(tmp==Gcd+)tmp=-;
return tmp;
}
void Dfs(int x)
{
f[x]=;
for(int i=head[x];i;i=e[i].pre)
{
int v=e[i].v;
if(f[v])continue;
d[v]=d[x]+e[i].t;Dfs(v);
}
maxx=max(maxx,d[x]);
minn=min(minn,d[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d%d",&x,&y),Add(x,y,),Add(y,x,-);
for(int i=;i<=n;i++)
if(dfn[i]==)Tarjan(i);
Gcd=Get_gcd();ans=Get_min();
if(Gcd)
{
if(Gcd<)Gcd=ans=-;
printf("%d %d\n",Gcd,ans);
return ;
}
ans=;memset(f,,sizeof(f));
for(int i=;i<=n;i++)
if(f[i]==)
{
maxx=;minn=maxn;Dfs(i);
ans+=maxx-minn+;
}
if(ans>)printf("%d 3\n",ans);
else printf("-1 -1\n");
return ;
}