#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int N=2e5+10;
const int M=2e6+10;
int n,m,ans1,ans2,mi,ma,tot,d[N],v[M],w[M],next[M],head[M];
bool vis[N];
inline int read(){
register int x=0,f=1;
register char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
void add(int x,int y,int z){
v[++tot]=y;w[tot]=z;next[tot]=head[x];head[x]=tot;
}
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
void tarjan(int x){//判断是否有环
vis[x]=1;
for(int i=head[x];i;i=next[i])
if(vis[v[i]]) ans1=gcd(ans1,abs(d[x]+w[i]-d[v[i]]));
else d[v[i]]=d[x]+w[i],tarjan(v[i]);
}
void dfs(int x){
vis[x]=1;
ma=max(ma,d[x]),mi=min(mi,d[x]);
for(int i=head[x];i;i=next[i])
if(!vis[v[i]]) d[v[i]]=d[x]+w[i],dfs(v[i]);
}
int main(){
n=read();m=read();
for(int i=1,a,b;i<=m;i++) a=read(),b=read(),add(a,b,1),add(b,a,-1);
for(int i=1;i<=n;i++) if(!vis[i]) tarjan(i);
if(ans1) for(ans2=3;ans2<ans1&&ans1%ans2;ans2++);//有环
else{//无环
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++){
if(!vis[i]){
ma=mi=d[i]=0;
dfs(i);
ans1+=ma-mi+1;
}
}
ans2=3;
}
if(ans1<3) ans1=ans2=-1;
printf("%d %d\n",ans1,ans2);
return 0;
}
