#include <bits/stdc++.h> using namespace std;

const int maxm=1000100,maxn=100100; struct stu { int x,y; }edge[maxm]; struct lily t1.y<t2.y:t1.x<t2.x; }

int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); }

void dfs(int now,int t) { if(!book[now]) { book[now]=1; d[now].id=t; l1=min(l1,t); l2=max(l2,t); for(int i=0;i<d[now].zb.size();i++) { int to=d[now].zb[i]; dfs(to,t+1); } for(int i=0;i<d[now].fb.size();i++) { int to=d[now].fb[i]; dfs(to,t-1); } } else ans=gcd(ans,abs(t-d[now].id)); }

int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&edge[i].x,&edge[i].y); sort(edge+1,edge+1+m,cmp); for(int i=1;i<=m;i++) { int x=edge[i].x,y=edge[i].y; if(x!=edge[i-1].x||y!=edge[i-1].y) { d[x].zb.push_back(y); d[y].fb.push_back(x); } } for(int i=1;i<=n;i++) { if(!book[i]) { dfs(i,0); l+=l2-l1+1; l2=l1=0; } } if(ans>=3) { for(int i=3;i<=ans;i++) { if(ans%i0) { printf("%d %d\n",ans,i); return 0; } } } if(ans0&&l>=3) { printf("%d 3\n",l); return 0; } printf("-1 -1\n"); return 0; }