#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200010;
const int M=4000100;
int n,m,tot,maxn,minn,ansmin,ansmax;
int dis[N],head[N],vis[N],ver[M],nxt[M],edge[M];
void add(int u,int v,int d)
{
    tot++;
    nxt[tot]=head[u];
    ver[tot]=v;
    edge[tot]=d;
    head[u]=tot;
}
int gcd(int x,int y)
{
    if(!y) return x;
    return gcd(y,x%y);
}
void dfs1(int x,int fa)//找环 
{
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int v=ver[i];
        if(v!=fa)
        {
            if(!vis[v])vis[v]=1,dis[v]=dis[x]+edge[i],dfs1(v,x);
            else ansmax=gcd(ansmax,abs(dis[x]-dis[v]+edge[i]));
        }
    }
}
void dfs2(int x,int fa)//处理森林 
{
    vis[x]=1;
    maxn=max(dis[x],maxn);
    minn=min(minn,dis[x]);
    for(int i=head[x];i;i=nxt[i])
    {
        int v=ver[i];
        if(v!=fa)
            if(!vis[v])
                vis[v]=1,dis[v]=dis[x]+edge[i],dfs2(v,x);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b; scanf("%d%d",&a,&b);
        add(a,b,1); add(b,a,-1);
    }
    for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i,0);
    if(ansmax) for(ansmin=3;ansmin<=ansmax&&ansmax%ansmin;ansmin++);
    else
    {
        ansmin=3;memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            if(!vis[i])
            {
                maxn=minn=0,dis[i]=0;
                dfs2(i,0);ansmax+=maxn-minn+1;
            }
    }
    if(ansmax<=2) ansmax=ansmin=-1;
    printf("%d %d\n",ansmax,ansmin);
    return 0;
}