#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std ;

#define addedge( s , t , d ) E[ s ].push_back( edge( t , d ) )

const int maxn = 100100 , inf = 0x7fffffff ;

struct edge {
int t , d ;
edge( int _t , int _d ) : t( _t ) , d( _d ) {
}
} ;
vector < edge > E[ maxn ] ;

int n , m , len = 0 ;

int gcd( int x , int y ) {
if ( x < y ) swap( x , y ) ;
int k ;
while ( y ) {
k = x % y ;
x = y ;
y = k ;
}
return x ;
}

int dfn[ maxn ] , maxd , mind ;
bool used[ maxn ] ;

void dfs( int now ) {
used[ now ] = true , maxd = max( maxd , dfn[ now ] ) , mind = min( mind , dfn[ now ] ) ;
for ( vector < edge > :: iterator p = E[ now ].begin( ) ; p != E[ now ].end( ) ; ++ p ) if ( ! used[ p -> t ] ) {
dfn[ p -> t ] = dfn[ now ] + p -> d ;
dfs( p -> t ) ;
} else len = gcd( len , abs( dfn[ p -> t ] - ( dfn[ now ] + p -> d ) ) ) ;
}

vector < int > ve ;

void travel( int now ) {
dfn[ now ] = 1 , ve.push_back( now ) ;
for ( vector < edge > :: iterator p = E[ now ].begin( ) ; p != E[ now ].end( ) ; ++ p ) if ( ! dfn[ p -> t ] ) travel( p -> t ) ;
}

int ans = 0 ;

int main( ) {
scanf( "%d%d" , &n , &m ) ;
while ( m -- ) {
int s , t ; scanf( "%d%d" , &s , &t ) ;
addedge( s , t , 1 ) , addedge( t , s , -1 ) ;
}
memset( dfn , 0 , sizeof( dfn ) ) ;
memset( used , false , sizeof( used ) ) ;
for ( int i = 0 ; i ++ < n ; ) if ( ! used[ i ] ) {
dfn[ i ] = 1 , maxd = - inf , mind = inf ;
dfs( i ) ;
ans += maxd - mind + 1 ;
}
if ( len ) {
if ( len < 3 ) printf( "-1 -1\n" ) ; else {
int x = inf , y = sqrt( len ) ;
for ( int i = 0 ; i ++ < y ; ) if ( ! ( len % i ) ) {
if ( i >= 3 ) x = min( x , i ) ;
if ( len / i >= 3 ) x = min( x , len / i ) ;
}
printf( "%d %d\n" , len , x ) ;
}
} else {
if ( ans < 3 ) printf( "-1 -1\n" ) ; else printf( "%d 3\n" , ans ) ;
}
return 0 ;
}