AC

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100000 + 10; const int M = 1000000 + 10;

struct Edge {

int to, w, next;

} e[M]; int head[N], tot; int n, m; int d[N], v[N]; int ans;

void add(int u, int v, int w) {

e[++tot] = (Edge){v, w, head[u]};
head[u] = tot;

}

int gcd(int a, int b) {

return b ? gcd(b, a % b) : a;

}

void dfs(int u) {

v[u] = 1;
for (int i = head[u]; i; i = e[i].next) {
    int to = e[i].to, w = e[i].w;
    if (!v[to]) {
        d[to] = d[u] + w;
        dfs(to);
    } else {
        ans = gcd(ans, abs(d[u] + w - d[to]));
    }
}

}

int mx, mn; void dfs2(int u) {

v[u] = 1;
mx = max(mx, d[u]);
mn = min(mn, d[u]);
for (int i = head[u]; i; i = e[i].next) {
    int to = e[i].to, w = e[i].w;
    if (!v[to]) {
        d[to] = d[u] + w;
        dfs2(to);
    }
}

}

int main() {

scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    add(a, b, 1);
    add(b, a, -1);
}
memset(v, 0, sizeof(v));
for (int i = 1; i <= n; i++) {
    if (!v[i]) {
        dfs(i);
    }
}
if (ans != 0) {
    if (ans < 3) {
        printf("-1 -1\n");
        return 0;
    }
    int min_k = 0;
    for (int i = 3; i <= ans; i++) {
        if (ans % i == 0) {
            min_k = i;
            break;
        }
    }
    if (min_k == 0) {
        printf("-1 -1\n");
    } else {
        printf("%d %d\n", ans, min_k);
    }
} else {
    memset(v, 0, sizeof(v));
    memset(d, 0, sizeof(d));
    int total = 0;
    for (int i = 1; i <= n; i++) {
        if (!v[i]) {
            mx = mn = d[i] = 0;
            dfs2(i);
            total += mx - mn + 1;
        }
    }
    if (total < 3) {
        printf("-1 -1\n");
    } else {
        printf("%d %d\n", total, 3);
    }
}
return 0;

}