【题目大意】：
    给定n个人，分别戴着k类面具(k>=3,k未知)，其中戴着i类面具的人能看见第i%k+1类人的面具，给定一些人互相看到的关系，求k的最大最小值
【题目解法】：
    感觉非常神奇！！
    首先大概把图分为三种：

    1.每条边无向后为一棵树，那么就是森林中每棵树的最长链之和即为答案，最小值为3
    2.有环，然后环上点的个数一定是答案的倍数，找出环后gcd即可
    3.没有环，但是转成无向图后有环，那么我们可以发现，如果有两条链的话，那么答案为链长的差值(多条链的话以此类推)
    然后这样不好搞
    网上有种神奇的做法，就是把a可以看到b，那么连边(a,b,1) (b,a,-1)，这样子我们用c[x]表示到x点的路径权值和，然后如果一个点被到达两次，那么两次的c值相减就是环的大小，并且可以把2，3情况一起考虑
    然后就是如果又有环，又有链，那么显然链就没用了...
    然后就是细节：注意枚举的点不一定是链的顶端，所以并不是所有的点c[i]都大于1!!

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100005;
const int M=2000005;
struct edge {int x,y,next;} b[M]; bool v[N];
int n,m,tot,a[N],ansmax,ansmin,dmin,dmax,c[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void addedge(int x,int y,int z)
{
    ++tot; b[tot].x=y; b[tot].y=z; b[tot].next=a[x]; a[x]=tot;
}
int gcd(int x,int y)
{
    if (y==0) return x; else return gcd(y,x%y);
}
void init()
{
    n=getint(); m=getint();
    for (int i=1; i<=m; i++)
    {
        int x=getint(),y=getint();
        addedge(x,y,1); addedge(y,x,-1);
    }
}
void dfs1(int x)
{
    v[x]=false;
    for (int p=a[x];p;p=b[p].next)
    {
        int pp=b[p].x;
        if (!v[pp]) {ansmax=gcd(ansmax,abs(c[x]+b[p].y-c[pp])); continue;}
        c[pp]=c[x]+b[p].y; dfs1(pp);
    }
}
void dfs2(int x)
{
    v[x]=false; dmax=max(dmax,c[x]); dmin=min(dmin,c[x]);
    for (int p=a[x];p;p=b[p].next)
    {
        int pp=b[p].x; if (v[pp]==false) continue;
        c[pp]=c[x]+b[p].y; dfs2(pp);
    }
}
void solve()
{
    memset(v,true,sizeof(v)); memset(c,0,sizeof(c));
    for (int i=1; i<=n; i++) if (v[i]) dfs1(i);//找环 
    if (ansmax==0) //处理链的情况 注意枚举的点不一定是链的顶端，所以并不是所有的点c[i]都大于1!! 
    {
        memset(v,true,sizeof(v)); memset(c,0,sizeof(c));
        for (int i=1; i<=n; i++)
        {
            if (!v[i]) continue; dmin=dmax=1;
            c[i]=1; dfs2(i); ansmax+=(dmax-dmin+1);
        }
        ansmin=3; //!!! 
    }
    else for (int i=3; i<=ansmax; i++) if (ansmax%i==0) {ansmin=i; break;}
    if ((ansmax<3)||(ansmin<3)) printf("-1 -1\n"); else printf("%d %d\n",ansmax,ansmin);
}
int main()
{
    init();
    solve();
    return 0;
}