原題見
這里（BZOJ和BSOJ都掛了，真杯具，只能借助RQ了囧……）
難度不是很大，就是特殊情況比較多，比較猥瑣（不過本題數據弱，就算不考慮所有的特殊情況也能過7個點）。
首先O(NM)的樸素算法很好想到：枚舉K，然后給每個結點編號即可。在編號時，先隨便指定一個未編號的點，設它的編號為0，然后遍歷所有和它相關聯的邊（這里可以把原圖想象成一個無向圖），將這些邊的另一個端點編上號即可，中間若某個點的編號出現矛盾，則這個K不合法，否則這個K合法。
然后進行優化：合法的K實際上是有限制的，它必然是某個數的因數，具體來說，對這個圖進行DFS，并考察其中所有的跨越邊和逆向邊，對于跨越邊<i, j>，設遍歷樹中i、j間距離為D，則合法的K必然是(D-1)的因數（因為i和遍歷樹中j的父結點都有指向j的邊，它們的編號應相同，而它們之間的距離為(D-1)）；對于逆向邊<i, j>，設遍歷樹中i、j間距離為D'，則合法的K必然是(D'+1)的因數（因為這里形成了一個環，環的長度為(D'+1)）。這樣一來就明顯縮小了K的取值范圍，再進行枚舉，就可以顯著縮短時間。
下面是一些極其猥瑣的特殊情況：
（1）根據題意，必須是K類每類都有，因此在嘗試編號成功（沒有發生任何矛盾）后，還要看一下
實際出現的編號數目是否等于K，若小于K，同樣不合法；
（2）該圖的基圖可能不連通，此時對于其基圖的每個連通塊，其編號互不影響，所以要對每個連通塊分別統計實際出現的編號數目，設它們的和為SUM，則不大于SUM的K值均合法（只要中間不出現矛盾），因此可以直接得到最大值為SUM，提前結束；不過，這種特判只有在總共實際出現的編號數目小于K的情況下才能進行；
（3）由于考察的是實際出現的編號數目，因此最后求出的最大值、最小值可能小于3，這時應作出如下處理：若最大值小于3，則無解；若最小值小于3，則將最小值改為3。
本題比較猥瑣的數據是第4、5、6個點，分別出現了上述的第（1）、（2）、（3）種特殊情況，此外，這三個點建出的圖中竟然沒有一條跨越邊或逆向邊！
代碼：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = 100000, MAXM = 1100001;
struct edge {
int a, b, s, pre, next;
} E0[MAXM], E[MAXM + MAXM];
int n, m0, m, P, len, X[MAXN], No[MAXN], stk[MAXN], st[MAXN], dep[MAXN], V[MAXN], fo[MAXN], Q[MAXN], res0, res1;
bool vst[MAXN], T0[MAXN];
long long T[MAXN], _Z = 0;
void init_d()
{
re(i, n) E[i].a = E[i].pre = E[i].next = E0[i].a = E0[i].pre = E0[i].next = i;
m0 = n; if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E[m].a = a; E[m].b = b; E[m].s = 1; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
E[m].a = b; E[m].b = a; E[m].s = -1; E[m].pre = E[b].pre; E[m].next = b; E[b].pre = m; E[E[m].pre].next = m++;
}
void init()
{
freopen("party.in", "r", stdin);
int _m, a, b; scanf("%d%d", &n, &_m); init_d();
re(i, _m) {
scanf("%d%d", &a, &b);
add_edge(--a, --b);
}
fclose(stdin);
}
int gcd(int a, int b)
{
int r;
while (b) {
r = a % b; a = b; b = r;
}
return a;
}
void prepare()
{
int tp, x, y, ord = 0;
bool fd;
re(i, n) V[i] = 0; P = 0;
re(i, n) if (!V[i]) {
stk[tp = 0] = i; fo[i] = ord++; V[i] = 1; st[i] = E0[i].next; dep[i] = 0;
while (tp >= 0) {
x = stk[tp]; fd = 0;
for (int p=st[x]; p != x; p=E0[p].next) {
y = E0[p].b;
if (!V[y]) {
stk[++tp] = y; fo[y] = ord++; V[y] = 1; st[y] = E0[y].next; dep[y] = dep[x] + 1; st[x] = E0[p].next; fd = 1; break;
} else if (V[y] == 1) P = gcd(P, dep[x] - dep[y] + 1); else if (fo[y] > fo[x]) P = gcd(P, dep[y] - dep[x] - 1);
}
if (!fd) {V[x] = 2; tp--;}
}
}
len = 0; re3(i, 3, n) if (!(P % i)) X[len++] = i;
}
int test(int K)
{
re(i, n) {vst[i] = 0; No[i] = -1;}
re(i, K) T0[i] = 0;
int x, y, No0, sum = 0, sum0 = 0;
re(i, n) if (!vst[i]) {
No[i] = 0; Q[0] = i; vst[i] = 1; _Z++; if (T[0] != _Z) {T[0] = _Z; sum++;} if (!T0[0]) {T0[0] = 1; sum0++;}
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=E[x].next; p != x; p=E[p].next) {
y = E[p].b; No0 = No[x] + E[p].s;
if (No0 == K) No0 = 0; else if (No0 == -1) No0 = K - 1;
if (No[y] >= 0 && No0 != No[y]) return -1; else {
No[y] = No0;
if (T[No0] != _Z) {T[No0] = _Z; sum++;}
if (!T0[No0]) {T0[No0] = 1; sum0++;}
}
if (!vst[y]) {vst[y] = 1; Q[++rear] = y;}
}
}
}
if (sum0 < K) res0 = sum;
return sum0;
}
void solve()
{
int K, K0; res0 = res1 = -1;
re(i, len) {
K = X[i]; K0 = test(K);
if (K0 != -1) {
if (res1 == -1) res1 = K0;
if (K0 < K) break; else res0 = K;
}
}
if (res0 < 3) res0 = res1 = -1; else if (res1 < 3) res1 = 3;
}
void pri()
{
freopen("party.out", "w", stdout);
printf("%d %d\n", res0, res1);
fclose(stdout);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}